{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sudoku Solver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: solveSudoku"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #解数独"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一个程序，通过填充空格来解决数独问题。</p>\n",
    "\n",
    "<p>数独的解法需<strong> 遵循如下规则</strong>：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>数字&nbsp;<code>1-9</code>&nbsp;在每一行只能出现一次。</li>\n",
    "\t<li>数字&nbsp;<code>1-9</code>&nbsp;在每一列只能出现一次。</li>\n",
    "\t<li>数字&nbsp;<code>1-9</code>&nbsp;在每一个以粗实线分隔的&nbsp;<code>3x3</code>&nbsp;宫内只能出现一次。（请参考示例图）</li>\n",
    "</ol>\n",
    "\n",
    "<p>数独部分空格内已填入了数字，空白格用&nbsp;<code>'.'</code>&nbsp;表示。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<div class=\"top-view__1vxA\">\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/12/250px-sudoku-by-l2g-20050714svg.png\" style=\"height:250px; width:250px\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "<strong>输出：</strong>[[\"5\",\"3\",\"4\",\"6\",\"7\",\"8\",\"9\",\"1\",\"2\"],[\"6\",\"7\",\"2\",\"1\",\"9\",\"5\",\"3\",\"4\",\"8\"],[\"1\",\"9\",\"8\",\"3\",\"4\",\"2\",\"5\",\"6\",\"7\"],[\"8\",\"5\",\"9\",\"7\",\"6\",\"1\",\"4\",\"2\",\"3\"],[\"4\",\"2\",\"6\",\"8\",\"5\",\"3\",\"7\",\"9\",\"1\"],[\"7\",\"1\",\"3\",\"9\",\"2\",\"4\",\"8\",\"5\",\"6\"],[\"9\",\"6\",\"1\",\"5\",\"3\",\"7\",\"2\",\"8\",\"4\"],[\"2\",\"8\",\"7\",\"4\",\"1\",\"9\",\"6\",\"3\",\"5\"],[\"3\",\"4\",\"5\",\"2\",\"8\",\"6\",\"1\",\"7\",\"9\"]]\n",
    "<strong>解释：</strong>输入的数独如上图所示，唯一有效的解决方案如下所示：\n",
    "\n",
    "<img src=\" https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/12/250px-sudoku-by-l2g-20050714_solutionsvg.png\" style=\"height:250px; width:250px\" />\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>board.length == 9</code></li>\n",
    "\t<li><code>board[i].length == 9</code></li>\n",
    "\t<li><code>board[i][j]</code> 是一位数字或者 <code>'.'</code></li>\n",
    "\t<li>题目数据 <strong>保证</strong> 输入数独仅有一个解</li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sudoku-solver](https://leetcode.cn/problems/sudoku-solver/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sudoku-solver](https://leetcode.cn/problems/sudoku-solver/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        self.backtracking(board)\n",
    "    def backtracking(self,board):\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j]!='.':\n",
    "                    continue\n",
    "                for k in range(1,10):\n",
    "                    if self.isvalid(i,j,k,board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board):\n",
    "                            return True\n",
    "                        board[i][j] = '.'\n",
    "                return False\n",
    "        return True\n",
    "    def isvalid(self,row,col,val,board):\n",
    "        for i in range(9):\n",
    "            if board[row][i]==str(val):\n",
    "                return False\n",
    "        for j in range(9):\n",
    "            if board[j][col]==str(val):\n",
    "                return False\n",
    "        start_row = (row//3)*3\n",
    "        start_col = (col//3)*3\n",
    "        for i in range(start_row,start_row+3):\n",
    "            for j in range(start_col,start_col+3):\n",
    "                if board[i][j]==str(val):\n",
    "                    return False\n",
    "        return True\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        return main(board)\n",
    "\n",
    "def main(board):\n",
    "    sub_board = {}\n",
    "    row_board = {row: {1, 2, 3, 4, 5, 6, 7, 8, 9} for row in range(9)}\n",
    "    col_board = {col: {1, 2, 3, 4, 5, 6, 7, 8, 9} for col in range(9)}\n",
    "    entry = {}\n",
    "    for row_no in [0, 1, 2]:\n",
    "        for col_no in [0, 1, 2]:\n",
    "            sub_board_no = (row_no, col_no)\n",
    "            temp_set = {1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
    "            for i in range(row_no * 3, row_no * 3 + 3):\n",
    "                for j in range(col_no * 3, col_no * 3 + 3):\n",
    "                    if board[i][j] != '.':\n",
    "                        temp_set.remove(int(board[i][j]))\n",
    "                        row_board[i].remove(int(board[i][j]))\n",
    "                        col_board[j].remove(int(board[i][j]))\n",
    "                    else:\n",
    "                        entry[(i, j)] = set()\n",
    "            sub_board[sub_board_no] = temp_set\n",
    "\n",
    "    for key in entry.keys():\n",
    "        i, j = key\n",
    "        entry[key] = row_board[i] & col_board[j] & sub_board[(i // 3, j // 3)]\n",
    "\n",
    "    input_params = []\n",
    "    for xy, val in entry.items():\n",
    "        line = [0, xy[0], xy[1]] + list(val)\n",
    "        line[0] = len(line)\n",
    "        heapq.heappush(input_params, line)    \n",
    "\n",
    "    result = search(input_params, {})\n",
    "    for (i, j), val in result.items():\n",
    "        board[i][j] = str(val)\n",
    "    return result\n",
    "\n",
    "def search(heap, record, d=0):\n",
    "    if len(heap) == 1:\n",
    "        i, j = heap[0][1], heap[0][2]\n",
    "        val = heap[0][3]\n",
    "        record[(i, j)] = val\n",
    "        return record\n",
    "    else:\n",
    "        item = heapq.heappop(heap)\n",
    "        i, j, val_list = item[1], item[2], item[3:]\n",
    "        for val in val_list:\n",
    "            new_heap = []\n",
    "            deadend = False  # this val is not valid\n",
    "\n",
    "            for this_item in heap:\n",
    "                x, y, tmp_val_set = this_item[1], this_item[2], this_item[3:]\n",
    "                if i//3 == x//3 and j//3 == y//3 and val in tmp_val_set:\n",
    "                    tmp_val_set.remove(val)\n",
    "\n",
    "                if i == x and val in tmp_val_set:\n",
    "                    tmp_val_set.remove(val)\n",
    "\n",
    "                if j == y and val in tmp_val_set:\n",
    "                    tmp_val_set.remove(val)\n",
    "\n",
    "                if not tmp_val_set:\n",
    "                    deadend = True\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappush(new_heap, [len(tmp_val_set), x, y] + tmp_val_set)\n",
    "            \n",
    "            if deadend:\n",
    "                continue\n",
    "            else:\n",
    "                # all removals passed\n",
    "                new_record = copy.copy(record)\n",
    "                new_record[(i, j)] = val\n",
    "                res = search(new_heap, new_record, d+1)\n",
    "                if res is None:\n",
    "                    continue\n",
    "                else:\n",
    "                    return res\n",
    "        return None\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Array:\n",
    "\n",
    "    def createArray(*dimensions):\n",
    "        if len(dimensions) == 1:\n",
    "            return [0] * dimensions[0]\n",
    "        \n",
    "        a = []\n",
    "        for _ in range(dimensions[0]):\n",
    "            a.append(Array.createArray(*dimensions[1:]))\n",
    "        return a\n",
    "\n",
    "    def copyArray(array):\n",
    "        if not isinstance(array, list):\n",
    "            return array\n",
    "\n",
    "        a = []\n",
    "        for v in array:\n",
    "            a.append(Array.copyArray(v))\n",
    "        return a\n",
    "\n",
    "    def copyArrayTo(src, dst):\n",
    "        for i in range(len(dst)):\n",
    "            if isinstance(src[i], list) and isinstance(dst[i], list):\n",
    "                Array.copyArrayTo(src[i], dst[i])\n",
    "            else:\n",
    "                dst[i] = src[i]\n",
    "\n",
    "class Constraint:\n",
    "\n",
    "    def __init__(self, board: List[List[str]]) -> None:\n",
    "        self.rows = Array.createArray(9, 9)\n",
    "        self.columns = Array.createArray(9, 9)\n",
    "        self.boxes = Array.createArray(3, 3, 9)\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if isinstance(board[i][j], str) and board[i][j] != \".\":\n",
    "                    index = int(board[i][j]) - 1\n",
    "\n",
    "                    self.add(i, j, index)\n",
    "\n",
    "                    if self.isInvalid(i, j, index):\n",
    "                        print(\"The Sudoku can't be solved\")\n",
    "                        return\n",
    "\n",
    "    def isEmpty(self, i, j, index) -> bool:\n",
    "        return self.rows[i][index] == 0 and self.columns[j][index] == 0 and self.boxes[i // 3][j // 3][index] == 0\n",
    "\n",
    "    def isInvalid(self, i, j, index) -> bool:\n",
    "        return self.rows[i][index] > 1 or self.columns[j][index] > 1 or self.boxes[i // 3][j // 3][index] > 1\n",
    "\n",
    "    def add(self, i, j, index) -> None:\n",
    "        self.rows[i][index] += 1\n",
    "        self.columns[j][index] += 1\n",
    "        self.boxes[i // 3][j // 3][index] += 1\n",
    "\n",
    "class Rangement:\n",
    "\n",
    "    def __init__(self, board: List[List]) -> None:\n",
    "        self.rows = Array.createArray(9, 9)\n",
    "        self.columns = Array.createArray(9, 9)\n",
    "        self.boxes = Array.createArray(3, 3, 9)\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if isinstance(board[i][j], list):\n",
    "                    for k in range(len(board[i][j])):\n",
    "                        index = board[i][j][k] - 1\n",
    "\n",
    "                        self.rows[i][index] += 1\n",
    "                        self.columns[j][index] += 1\n",
    "                        self.boxes[i // 3][j // 3][index] += 1\n",
    "\n",
    "    def applyConstraint(self, board: List[List], i, j, constraint) -> bool:\n",
    "        if not isinstance(board[i][j], list):\n",
    "            return True\n",
    "\n",
    "        k = len(board[i][j]) - 1\n",
    "        while k >= 0:\n",
    "            index = board[i][j][k] - 1\n",
    "\n",
    "            if not constraint.isEmpty(i, j, index):\n",
    "                board[i][j].pop(k)\n",
    "                \n",
    "                self.rows[i][index] -= 1\n",
    "                self.columns[j][index] -= 1\n",
    "                self.boxes[i // 3][j // 3][index] -= 1\n",
    "\n",
    "            k -= 1\n",
    "        \n",
    "        return len(board[i][j]) > 0\n",
    "\n",
    "    def remove(self, i, j, index):\n",
    "        self.rows[i][index] -= 1\n",
    "        self.columns[j][index] -= 1\n",
    "        self.boxes[i // 3][j // 3][index] -= 1\n",
    "\n",
    "    def allowOneValue(self, i, j, index):\n",
    "        return self.rows[i][index] == 1 or self.columns[j][index] == 1 or self.boxes[i // 3][j // 3][index] == 1\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        constraint = Constraint(board)\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    board[i][j] = [index + 1 for index in range(9) if constraint.isEmpty(i, j, index)]\n",
    "\n",
    "        rangement = Rangement(board)\n",
    "\n",
    "        # print(board)\n",
    "        \n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if isinstance(board[i][j], list):\n",
    "                    self.applyConstraint(board, i, j, constraint, rangement)\n",
    "\n",
    "                    if isinstance(board[i][j], str):\n",
    "                        self.propagate(board, i, j, constraint, rangement)\n",
    "\n",
    "        self.solveR(board)\n",
    "    \n",
    "        # print()\n",
    "        # for i in range(9):\n",
    "        #     print(board[i])\n",
    "\n",
    "    def propagate(self, board, r, c, constraint: Constraint, rangement: Rangement):\n",
    "        for i in range(9):\n",
    "            j = c\n",
    "            if isinstance(board[i][j], list):\n",
    "                if not self.applyConstraint(board, i, j, constraint, rangement):\n",
    "                    return False\n",
    "\n",
    "                if isinstance(board[i][j], str):\n",
    "                    if not self.propagate(board, i, j,constraint, rangement):\n",
    "                        return False\n",
    "\n",
    "        for j in range(9):\n",
    "            i = r\n",
    "            if isinstance(board[i][j], list):\n",
    "                if not self.applyConstraint(board, i, j,constraint, rangement):\n",
    "                    return False\n",
    "\n",
    "                if isinstance(board[i][j], str):\n",
    "                    if not self.propagate(board, i, j,constraint, rangement):\n",
    "                        return False\n",
    "\n",
    "        for i in range(r // 3, r // 3 + 3):\n",
    "            for j in range(c // 3, c // 3 + 3):\n",
    "                if isinstance(board[i][j], list):\n",
    "                    if not self.applyConstraint(board, i, j,constraint, rangement):\n",
    "                        return False\n",
    "\n",
    "                    if isinstance(board[i][j], str):\n",
    "                        if not self.propagate(board, i, j,constraint, rangement):\n",
    "                            return False\n",
    "\n",
    "        return True\n",
    "\n",
    "    def applyConstraint(self, board, i, j, constraint: Constraint, rangement: Rangement):\n",
    "        if not isinstance(board[i][j], list):\n",
    "            return True\n",
    "\n",
    "        if not rangement.applyConstraint(board, i, j, constraint):\n",
    "            return False\n",
    "\n",
    "        if len(board[i][j]) == 1:\n",
    "            index = board[i][j][0] - 1\n",
    "            board[i][j] = str(index + 1)\n",
    "\n",
    "            constraint.add(i, j, index)\n",
    "            rangement.remove(i, j, index)\n",
    "            return True\n",
    "            \n",
    "        k = len(board[i][j]) - 1\n",
    "        while k >= 0:\n",
    "            index = board[i][j][k] - 1\n",
    "\n",
    "            if rangement.allowOneValue(i, j, index):\n",
    "                break\n",
    "            \n",
    "            k -= 1\n",
    "\n",
    "        if k >= 0:\n",
    "            lst = board[i][j]\n",
    "\n",
    "            index = board[i][j][k] - 1\n",
    "            board[i][j] = str(index + 1)\n",
    "                \n",
    "            constraint.add(i, j, index)\n",
    "\n",
    "            for t in range(len(lst)):\n",
    "                index = lst[t] - 1\n",
    "                rangement.remove(i, j, index)\n",
    "\n",
    "        return True\n",
    "        \n",
    "    def solveR(self, board: List[List]) -> None:\n",
    "        # newboard = Array.copyArray(board)\n",
    "        \n",
    "        jumpOut = False\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if isinstance(board[i][j], list):\n",
    "                    \n",
    "                    k = len(board[i][j]) - 1\n",
    "                    while k >= 0:\n",
    "                        index = board[i][j][k] - 1\n",
    "\n",
    "                        newboard = Array.copyArray(board)\n",
    "                        c = Constraint(newboard)\n",
    "                        r = Rangement(newboard)\n",
    "\n",
    "                        newboard[i][j] = str(index + 1)\n",
    "                        c.add(i, j, index)\n",
    "                        r.remove(i, j, index)\n",
    "                        \n",
    "                        if not self.propagate(newboard, i, j, c, r):\n",
    "                            k -= 1\n",
    "                            continue\n",
    "                        \n",
    "                        if not self.solveR(newboard):\n",
    "                            return False\n",
    "\n",
    "                        k -= 1\n",
    "                        break\n",
    "\n",
    "                    for i in range(9):\n",
    "                        for j in range(9):\n",
    "                            board[i][j] = newboard[i][j]\n",
    "\n",
    "                    jumpOut = True\n",
    "                    return True\n",
    "\n",
    "            if jumpOut:\n",
    "                break\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def pre():\n",
    "            self.row = [set() for i in range(9)]\n",
    "            self.line = [set() for i in range(9)]\n",
    "            self.block = [set() for i in range(9)]\n",
    "            self.record = dict()\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if board[i][j] == '.':\n",
    "                        continue\n",
    "                    self.row[j].add(board[i][j])\n",
    "                    self.line[i].add(board[i][j])\n",
    "                    self.block[i // 3 * 3+ j // 3].add(board[i][j])\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if board[i][j] != '.':\n",
    "                        continue\n",
    "                    possible = set([str(_) for _ in range(1, 10)]) - self.row[j] - self.line[i] - self.block[i // 3 * 3+ j // 3] \n",
    "                    self.record[str(len(possible))+str(i)+str(j)] = possible\n",
    "            return\n",
    "\n",
    "        def back_track():\n",
    "            if not self.record:\n",
    "                return True\n",
    "            cur = min(self.record)\n",
    "            for candidate in self.record[cur]:\n",
    "                x = int(cur[1])\n",
    "                y = int(cur[2])\n",
    "                record_copy = deepcopy(self.record)\n",
    "                for one in self.record:\n",
    "                    if one == cur:\n",
    "                        continue\n",
    "                    x1, y1 = int(one[1]), int(one[2])\n",
    "                    if x1 == x or y1 == y or x1 //3 *3 + y1//3 == x //3 *3 + y //3:\n",
    "                        tmp = record_copy.pop(one)\n",
    "                        if candidate in tmp:\n",
    "                            tmp.remove(candidate)\n",
    "                        record_copy[str(len(tmp))+str(x1)+str(y1)] = tmp\n",
    "                record_copy, self.record = self.record, record_copy\n",
    "                board[x][y] = candidate\n",
    "                self.record.pop(cur)\n",
    "                if back_track():\n",
    "                    return True\n",
    "                else:\n",
    "                    self.record = record_copy\n",
    "                    board[x][y] = '.'\n",
    "        pre()\n",
    "        back_track()\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def get_all_possible(nums, i_row, i_column):\n",
    "            all_num = set(str(n) for n in range(1, 10))\n",
    "            left = set(nums[i_row]).union(set([row[i_column] for row in nums]))\n",
    "            row, column = i_row // 3, i_column // 3\n",
    "            for v in range(3):\n",
    "                left = left.union(set(nums[row * 3 + v][column * 3: (column + 1) * 3]))\n",
    "            return sorted(all_num.difference(left))\n",
    "\n",
    "        def is_solved(sudoku):\n",
    "            for row in sudoku:\n",
    "                if '.' in row:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def try_possible(sudoku, p_v=None, i_row=-1, i_column=-1):\n",
    "            if p_v:\n",
    "                sudoku[i_row][i_column] = p_v\n",
    "\n",
    "            p_dict, p_len = {}, {}\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if sudoku[i][j] == '.':\n",
    "                        p = get_all_possible(sudoku, i, j)\n",
    "                        if len(p) == 0:\n",
    "                            return False\n",
    "                        if len(p) == 1:\n",
    "                            return try_possible(sudoku, p.pop(), i, j)\n",
    "                        p_dict[(i, j)] = p\n",
    "                        p_len.setdefault(len(p), set()).add((i, j))\n",
    "\n",
    "            if not p_len and not p_dict and is_solved(sudoku):\n",
    "                return True\n",
    "\n",
    "            p_dict = sorted(p_dict.items(), key=lambda x: len(x[1]))\n",
    "            for index, values in p_dict:\n",
    "                for v in values:\n",
    "                    row, column = index\n",
    "                    sudoku_copy = [nums[:] for nums in sudoku]\n",
    "                    if try_possible(sudoku_copy, v, row, column):\n",
    "                        for r in range(9):\n",
    "                            for c in range(9):\n",
    "                                sudoku[r][c] = sudoku_copy[r][c]\n",
    "                        return True\n",
    "                return False\n",
    "\n",
    "            return True if is_solved(sudoku) else False\n",
    "\n",
    "        try_possible(board)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 行记录\n",
    "        self.hmap = []\n",
    "        # 列记录\n",
    "        self.lmap = []\n",
    "        # 分图记录\n",
    "        self.tmap = []\n",
    "        for i in range(9):\n",
    "            self.hmap.append([])\n",
    "            self.lmap.append([])\n",
    "            self.tmap.append([])\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    self.hmap[i].append(board[i][j])\n",
    "                    self.lmap[j].append(board[i][j])\n",
    "                    p = i // 3 * 3 + (j // 3)\n",
    "                    self.tmap[p].append(board[i][j])\n",
    "        self.playdSudoku(board)\n",
    "\n",
    "    def playdSudoku(self, board) -> bool:\n",
    "        key = []\n",
    "        asr = []\n",
    "        is_slave = False\n",
    "        slaves = []\n",
    "        for i in board:\n",
    "            key.append(i[:])\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if key[i][j] == '.':\n",
    "                    l = i // 3 * 3 + (j // 3)\n",
    "                    key[i][j] = []\n",
    "                    for k in range(1, 10):\n",
    "                        k = str(k)\n",
    "                        if k not in self.hmap[i] and k not in self.lmap[j] and k not in self.tmap[l]:\n",
    "                            key[i][j].append(k)\n",
    "                    if key[i][j] == []:\n",
    "                        return False\n",
    "                    elif len(key[i][j]) == 1:\n",
    "                        k = key[i][j][0]\n",
    "                        slaves.append([i, j, k])\n",
    "                        is_slave = True\n",
    "                    elif asr != [] and len(key[i][j]) < len(key[asr[0][0]][asr[0][1]]):\n",
    "                        asr.insert(0, [i, j])\n",
    "                    else:\n",
    "                        asr.append([i, j])\n",
    "                # 根据必须存在一个值确定一个一定对的值\n",
    "        for i, j in asr:\n",
    "            l_a = len(key[i][j])\n",
    "            if l_a > 1:\n",
    "                key_t = False\n",
    "                # 判断横行\n",
    "                for ki in key[i][j]:\n",
    "                    key_t = False\n",
    "                    for m in range(9):\n",
    "                        if m == j:\n",
    "                            continue\n",
    "                        if type(key[i][m]) == list:\n",
    "                            if ki in key[i][m] and len(key[i][m]) > 1:\n",
    "                                key_t = True\n",
    "                                break\n",
    "                            if ki in key[i][m] and len(key[i][m]) == 1:\n",
    "                                key[i][j].remove(ki)\n",
    "                                key_t = True\n",
    "                                break\n",
    "                    if key_t:\n",
    "                        continue\n",
    "                    for m in range(9):\n",
    "                        if m == j:\n",
    "                            continue\n",
    "                        if type(key[m][j]) == list:\n",
    "                            if ki in key[m][j] and len(key[m][j]) > 1:\n",
    "                                key_t = True\n",
    "                                break\n",
    "                            if ki in key[m][j] and len(key[m][j]) == 1:\n",
    "                                key[i][j].remove(ki)\n",
    "                                key_t = True\n",
    "                                break\n",
    "                    if key_t:\n",
    "                        continue\n",
    "                    m1 = i // 3 * 3\n",
    "                    n1 = j // 3 * 3\n",
    "                    for m in range(m1, m1 + 3):\n",
    "                        for n in range(n1, n1 + 3):\n",
    "                            if m == j and n == j:\n",
    "                                continue\n",
    "                            if type(key[m][j]) == list:\n",
    "                                if ki in key[m][n] and len(key[m][n]) > 1:\n",
    "                                    key_t = True\n",
    "                                    break\n",
    "                                if ki in key[m][n] and len(key[m][n]) == 1:\n",
    "                                    key[i][j].remove(ki)\n",
    "                                    key_t = True\n",
    "                                    break\n",
    "                    if key_t:\n",
    "                        continue\n",
    "                    key_t = ki\n",
    "                    break\n",
    "                if type(key_t) == str:\n",
    "                    is_slave = True\n",
    "                    key[i][j] == [key_t]\n",
    "                    slaves.append([i, j, key_t])                \n",
    "        if is_slave:\n",
    "            i, j, k = slaves[0]\n",
    "            l = i // 3 * 3 + (j // 3)\n",
    "            board[i][j] = k\n",
    "            self.hmap[i].append(k)\n",
    "            self.lmap[j].append(k)\n",
    "            self.tmap[l].append(k)\n",
    "\n",
    "            if self.playdSudoku(board):\n",
    "                return True\n",
    "            else:\n",
    "                i, j, k = slaves[0]\n",
    "                l = i // 3 * 3 + (j // 3)\n",
    "                self.lmap[j].remove(k)\n",
    "                self.hmap[i].remove(k)\n",
    "                self.tmap[l].remove(k)\n",
    "                board[i][j] = '.'\n",
    "        elif asr == []:\n",
    "            return True\n",
    "        else:\n",
    "            i, j = asr[0]\n",
    "            for k in key[i][j]:\n",
    "                board[i][j] = k\n",
    "                self.hmap[i].append(k)\n",
    "                self.lmap[j].append(k)\n",
    "                l = i // 3 * 3 + (j // 3)\n",
    "                self.tmap[l].append(k)\n",
    "                if self.playdSudoku(board):\n",
    "                    return True\n",
    "                else:\n",
    "                    self.lmap[j].pop(-1)\n",
    "                    self.hmap[i].pop(-1)\n",
    "                    self.tmap[l].pop(-1)\n",
    "                    board[i][j] = '.'\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DLX:\r\n",
    "    \"\"\"\r\n",
    "    十字交叉双向循环链表\r\n",
    "    \"\"\"\r\n",
    "\r\n",
    "    def __init__(self, n):\r\n",
    "        \"\"\"\r\n",
    "        :param n: 数独的阶数\r\n",
    "        \"\"\"\r\n",
    "        self.n = n\r\n",
    "        self.m = n ** 2 * n ** 2 * 4 + 1  # 总共的列数(标注节点数+头节点)\r\n",
    "        self.max_nums = n ** 2 * n ** 2 * n ** 2 * 4 + self.m  # 最大节点编号\r\n",
    "\r\n",
    "        # 用下标表示节点编号，下标0表示节点0（即头节点），下标1表示节点1，以此类推...\r\n",
    "        self.u = [0 for _ in range(self.max_nums)]  # 记录节点的上链接点\r\n",
    "        self.d = [0 for _ in range(self.max_nums)]  # 记录节点的下链接点\r\n",
    "        self.l = [0 for _ in range(self.max_nums)]  # 记录节点的左链接点\r\n",
    "        self.r = [0 for _ in range(self.max_nums)]  # 记录节点的右链接点\r\n",
    "        self.row = [0 for _ in range(self.max_nums)]  # 记录节点所在的行\r\n",
    "        self.col = [0 for _ in range(self.max_nums)]  # 记录节点所在的列\r\n",
    "\r\n",
    "        # 设置首行的上下左右链接关系\r\n",
    "        for i in range(self.m):\r\n",
    "            self.u[i] = i\r\n",
    "            self.d[i] = i\r\n",
    "            self.r[i] = i + 1\r\n",
    "            self.l[i] = i - 1\r\n",
    "            self.row[i] = 0\r\n",
    "            self.col[i] = i\r\n",
    "        self.head = 0\r\n",
    "        self.l[self.head] = self.m - 1\r\n",
    "        self.r[self.m - 1] = self.head\r\n",
    "\r\n",
    "        self.s = [0 for _ in range(self.m)]  # 记录每列节点个数，以便搜索时选择节点数最少的列删除（即优化搜索方向）\r\n",
    "\r\n",
    "        self.next_point = self.m  # 下一个节点编号\r\n",
    "\r\n",
    "        self.ans = [0 for _ in range(n ** 2 * n ** 2 * n ** 2)]  # 所有答案的集合\r\n",
    "        self.end = 0\r\n",
    "\r\n",
    "    def add_row(self, row, columns):\r\n",
    "        \"\"\"\r\n",
    "        :param row: 新增节点所在的行\r\n",
    "        :param columns: 新增节点所在的列\r\n",
    "        :return:\r\n",
    "        \"\"\"\r\n",
    "        first = self.next_point\r\n",
    "        self.l[first] = first\r\n",
    "        self.r[first] = first\r\n",
    "\r\n",
    "        for c in columns:\r\n",
    "            # 先增加新节点对上下左右节点的指向\r\n",
    "            self.u[self.next_point] = self.u[c]\r\n",
    "            self.d[self.next_point] = c\r\n",
    "            self.l[self.next_point] = self.l[first]\r\n",
    "            self.r[self.next_point] = first\r\n",
    "            self.row[self.next_point] = row\r\n",
    "            self.col[self.next_point] = c\r\n",
    "\r\n",
    "            # 然后修改上下左右节点的指向，即指向新节点\r\n",
    "            self.r[self.l[first]] = self.next_point\r\n",
    "            self.l[first] = self.next_point\r\n",
    "            self.d[self.u[c]] = self.next_point\r\n",
    "            self.u[c] = self.next_point\r\n",
    "\r\n",
    "            self.s[c] += 1  # 该列节点数+1\r\n",
    "\r\n",
    "            self.next_point += 1  # 节点编号+1\r\n",
    "\r\n",
    "    def remove(self, c):\r\n",
    "        \"\"\"\r\n",
    "        删除第c列\r\n",
    "        :param c:\r\n",
    "        :return:\r\n",
    "        \"\"\"\r\n",
    "        self.l[self.r[c]] = self.l[c]\r\n",
    "        self.r[self.l[c]] = self.r[c]\r\n",
    "\r\n",
    "        i = self.d[c]\r\n",
    "        while i != c:\r\n",
    "            j = self.r[i]\r\n",
    "            while j != i:\r\n",
    "                self.d[self.u[j]] = self.d[j]\r\n",
    "                self.u[self.d[j]] = self.u[j]\r\n",
    "                self.s[self.col[j]] -= 1\r\n",
    "                j = self.r[j]\r\n",
    "            i = self.d[i]\r\n",
    "\r\n",
    "    def restore(self, c):\r\n",
    "        \"\"\"\r\n",
    "        恢复第c列\r\n",
    "        :param c:\r\n",
    "        :return:\r\n",
    "        \"\"\"\r\n",
    "        i = self.u[c]\r\n",
    "        while i != c:\r\n",
    "            j = self.l[i]\r\n",
    "            while j != i:\r\n",
    "                self.d[self.u[j]] = j\r\n",
    "                self.u[self.d[j]] = j\r\n",
    "                self.s[self.col[j]] += 1\r\n",
    "                j = self.l[j]\r\n",
    "            i = self.u[i]\r\n",
    "        self.l[self.r[c]] = c\r\n",
    "        self.r[self.l[c]] = c\r\n",
    "\r\n",
    "    def dance(self, step):\r\n",
    "        \"\"\"\r\n",
    "        :param step: 递归深度\r\n",
    "        :return:\r\n",
    "        \"\"\"\r\n",
    "        if self.r[self.head] == self.head:\r\n",
    "            self.end = step\r\n",
    "            return True\r\n",
    "\r\n",
    "        c = self.r[self.head]\r\n",
    "        j = self.r[self.head]\r\n",
    "        # 选择节点数最少的列\r\n",
    "        while j != self.head:\r\n",
    "            if self.s[j] < self.s[c]:\r\n",
    "                c = j\r\n",
    "            j = self.r[j]\r\n",
    "        self.remove(c)\r\n",
    "\r\n",
    "        i = self.d[c]\r\n",
    "        while i != c:\r\n",
    "            # 删除节点i所在的行，并将其保存到结果集中\r\n",
    "            self.ans[step] = self.row[i]\r\n",
    "            j = self.r[i]\r\n",
    "            while j != i:\r\n",
    "                self.remove(self.col[j])\r\n",
    "                j = self.r[j]\r\n",
    "            if self.dance(step + 1):  # 搜索成功则返回\r\n",
    "                return True\r\n",
    "\r\n",
    "            # 搜索失败，要恢复，回溯\r\n",
    "            self.ans[step] = 0\r\n",
    "            j = self.l[i]\r\n",
    "            while j != i:\r\n",
    "                self.restore(self.col[j])\r\n",
    "                j = self.l[j]\r\n",
    "\r\n",
    "            i = self.d[i]\r\n",
    "        self.restore(c)\r\n",
    "        return False\r\n",
    "\r\n",
    "    def transform_input(self, i, j, num):\r\n",
    "        c1 = self.n ** 2 * (i - 1) + j\r\n",
    "        c2 = self.n ** 2 * self.n ** 2 + self.n ** 2 * (i - 1) + num\r\n",
    "        c3 = self.n ** 2 * self.n ** 2 * 2 + self.n ** 2 * (j - 1) + num\r\n",
    "        c4 = self.n ** 2 * self.n ** 2 * 3 + self.n ** 2 * ((i - 1) // self.n * self.n + (j - 1) // self.n) + num\r\n",
    "        return c1, c2, c3, c4\r\n",
    "\r\n",
    "    def run(self, input_str):\r\n",
    "        input_matrix = []\r\n",
    "        row_index = 1\r\n",
    "        for i in range(1, self.n ** 2 + 1):\r\n",
    "            for j in range(1, self.n ** 2 + 1):\r\n",
    "                if input_str[i - 1][j - 1] != '.':\r\n",
    "                    tmp = int(input_str[i - 1][j - 1])\r\n",
    "                    input_matrix.append((i, j, tmp))\r\n",
    "                    self.add_row(row_index, self.transform_input(i, j, tmp))\r\n",
    "                    row_index += 1\r\n",
    "                else:\r\n",
    "                    for k in range(1, self.n ** 2 + 1):\r\n",
    "                        input_matrix.append((i, j, k))\r\n",
    "                        self.add_row(row_index, self.transform_input(i, j, k))\r\n",
    "                        row_index += 1\r\n",
    "\r\n",
    "        if self.dance(0):\r\n",
    "            for i in self.ans[:self.end]:\r\n",
    "                input_str[input_matrix[i - 1][0] - 1][input_matrix[i - 1][1] - 1] = str(input_matrix[i - 1][2])\r\n",
    "        else:\r\n",
    "            print('Impossible')\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\r\n",
    "        dlx = DLX(3)\r\n",
    "        dlx.run(board)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def backtracking(board):\n",
    "            for i in range(len(board)):\n",
    "                for j in range(len(board[0])):\n",
    "                    if board[i][j] != '.':\n",
    "                        continue\n",
    "                    for k in range(1,10):\n",
    "                        if isValid(i,j,k,board):\n",
    "                            board[i][j] = str(k)\n",
    "                            if backtracking(board):\n",
    "                                return True\n",
    "                        board[i][j] = '.'\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def isValid(row,col,val,board):\n",
    "            for i in range(9):\n",
    "                if board[i][col] == str(val):\n",
    "                    return False\n",
    "            \n",
    "            for j in range(9):\n",
    "                if board[row][j] == str(val):\n",
    "                    return False\n",
    "\n",
    "            start_row = (row//3)*3\n",
    "            start_col = (col//3)*3\n",
    "            for i in range(start_row,start_row+3):\n",
    "                for j in range(start_col,start_col+3):\n",
    "                    if board[i][j] == str(val):\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        backtracking(board)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.board = None\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        all_set = set([\"1\",\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\"])\n",
    "        col_set = [copy.deepcopy(all_set) for i in range(9)]  #可用的数\n",
    "        row_set = [copy.deepcopy(all_set) for i in range(9)]\n",
    "        quare_set = [copy.deepcopy(all_set) for i in range(9)]\n",
    "        # print(row_set[0])\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != \".\":\n",
    "                    # print(board[i][j])\n",
    "                    row_set[i].remove(board[i][j])\n",
    "                    col_set[j].remove(board[i][j])\n",
    "                    quare_set[i // 3 * 3 + j // 3].remove(board[i][j])\n",
    "        \n",
    "        #########先使用简单的确定性填法######\n",
    "        while True:\n",
    "            change = 0\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    use_set = row_set[i] & col_set[j] & quare_set[i // 3 * 3 + j // 3]\n",
    "                    if board[i][j] == \".\" and len(use_set) == 1:\n",
    "                        specific_num = list(use_set)[0]\n",
    "                        board[i][j] = specific_num\n",
    "                        row_set[i].remove(specific_num)\n",
    "                        col_set[j].remove(specific_num)\n",
    "                        quare_set[i // 3 * 3 + j // 3].remove(specific_num)\n",
    "                        change += 1\n",
    "            if change == 0:\n",
    "                break\n",
    "\n",
    "        self.board = board\n",
    "        self.search(0, 0, col_set, row_set, quare_set)\n",
    "        return self.board\n",
    "    \n",
    "    def search(self, i, j, col_set, row_set, quare_set):\n",
    "        if i == 9:\n",
    "            return True\n",
    "        if self.board[i][j] != \".\":\n",
    "            if j == 8:\n",
    "                is_yes = self.search(i + 1, 0, col_set, row_set, quare_set)\n",
    "            else:\n",
    "                is_yes = self.search(i, j + 1, col_set, row_set, quare_set)\n",
    "            return is_yes\n",
    "        \n",
    "        use_set = row_set[i] & col_set[j] & quare_set[i // 3 * 3 + j // 3] #并集\n",
    "        for num in use_set:\n",
    "            self.board[i][j] = num\n",
    "            col_set_copy = copy.deepcopy(col_set)\n",
    "            row_set_copy = copy.deepcopy(row_set)\n",
    "            quare_set_copy = copy.deepcopy(quare_set)\n",
    "\n",
    "            col_set_copy[j].remove(num)\n",
    "            row_set_copy[i].remove(num)\n",
    "            quare_set_copy[i // 3 * 3 + j // 3].remove(num)\n",
    "\n",
    "            if j == 8:\n",
    "                is_yes = self.search(i + 1, 0, col_set_copy, row_set_copy, quare_set_copy)\n",
    "            else:\n",
    "                is_yes = self.search(i, j + 1, col_set_copy, row_set_copy, quare_set_copy)\n",
    "            \n",
    "            if is_yes:\n",
    "                return True\n",
    "            \n",
    "            self.board[i][j] = \".\"\n",
    "        return False\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 行记录\n",
    "        self.hmap = []\n",
    "        # 列记录\n",
    "        self.lmap = []\n",
    "        # 分图记录\n",
    "        self.tmap = []\n",
    "        for i in range(9):\n",
    "            self.hmap.append([])\n",
    "            self.lmap.append([])\n",
    "            self.tmap.append([])\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    self.hmap[i].append(board[i][j])\n",
    "                    self.lmap[j].append(board[i][j])\n",
    "                    p = i // 3 * 3 + (j // 3)\n",
    "                    self.tmap[p].append(board[i][j])\n",
    "        self.playdSudoku(board)\n",
    "\n",
    "    def playdSudoku(self, board) -> bool:\n",
    "        key = []\n",
    "        asr = []\n",
    "        is_slave = False\n",
    "        slaves = []\n",
    "        for i in board:\n",
    "            key.append(i[:])\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if key[i][j] == '.':\n",
    "                    l = i // 3 * 3 + (j // 3)\n",
    "                    key[i][j] = []\n",
    "                    for k in range(1, 10):\n",
    "                        k = str(k)\n",
    "                        if k not in self.hmap[i] and k not in self.lmap[j] and k not in self.tmap[l]:\n",
    "                            key[i][j].append(k)\n",
    "                    if key[i][j] == []:\n",
    "                        return False\n",
    "                    elif len(key[i][j]) == 1:\n",
    "                        k = key[i][j][0]\n",
    "                        slaves.append([i, j, k])\n",
    "                        is_slave = True\n",
    "                    elif asr != [] and len(key[i][j]) < len(key[asr[0][0]][asr[0][1]]):\n",
    "                        asr.insert(0, [i, j])\n",
    "                    else:\n",
    "                        asr.append([i, j])\n",
    "        if is_slave:\n",
    "            i, j, k = slaves[0]\n",
    "            l = i // 3 * 3 + (j // 3)\n",
    "            board[i][j] = k\n",
    "            self.hmap[i].append(k)\n",
    "            self.lmap[j].append(k)\n",
    "            self.tmap[l].append(k)\n",
    "\n",
    "            if self.playdSudoku(board):\n",
    "                return True\n",
    "            else:\n",
    "                i, j, k = slaves[0]\n",
    "                l = i // 3 * 3 + (j // 3)\n",
    "                self.lmap[j].remove(k)\n",
    "                self.hmap[i].remove(k)\n",
    "                self.tmap[l].remove(k)\n",
    "                board[i][j] = '.'\n",
    "        elif asr == []:\n",
    "            return True\n",
    "        else:\n",
    "            i, j = asr[0]\n",
    "            for k in key[i][j]:\n",
    "                board[i][j] = k\n",
    "                self.hmap[i].append(k)\n",
    "                self.lmap[j].append(k)\n",
    "                l = i // 3 * 3 + (j // 3)\n",
    "                self.tmap[l].append(k)\n",
    "                if self.playdSudoku(board):\n",
    "                    return True\n",
    "                else:\n",
    "                    self.lmap[j].pop(-1)\n",
    "                    self.hmap[i].pop(-1)\n",
    "                    self.tmap[l].pop(-1)\n",
    "                    board[i][j] = '.'\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def get_csp(pr, pc):\n",
    "            temp = copy.deepcopy(options)\n",
    "            for i in range(9):\n",
    "                if board[pr][i] in temp:\n",
    "                    temp.remove(str(board[pr][i]))\n",
    "                if board[i][pc] in temp:\n",
    "                    temp.remove(board[i][pc])\n",
    "            i_r, i_c = pr // 3 * 3, pc // 3 * 3\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if board[i_r + i][i_c + j] in temp:\n",
    "                        temp.remove(board[i_r + i][i_c + j])\n",
    "            return temp\n",
    "\n",
    "        def csp_update(pr, pc, csp):\n",
    "            for i in range(9):\n",
    "                if i > pc and (pr, i) in csp and board[pr][pc] in csp[pr, i]:\n",
    "                    csp[pr, i].remove(board[pr][pc])\n",
    "                    if len(csp[pr, i]) == 0:\n",
    "                        return False, {}\n",
    "                if i > pr and (i, pc) in csp and board[pr][pc] in csp[i, pc]:\n",
    "                    csp[i, pc].remove(board[pr][pc])\n",
    "                    if len(csp[i, pc]) == 0:\n",
    "                        return False, {}\n",
    "            i_r, i_c = pr // 3 * 3, pc // 3 * 3\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if (i > pr or j > pc) and (i_r + i, i_c + j) in csp and board[pr][pc] in csp[i_r + i, i_c + j]:\n",
    "                        csp[i_r + i, i_c + j].remove(board[pr][pc])\n",
    "                        if len(csp[i_r + i, i_c + j]) == 0:\n",
    "                            return False, {}\n",
    "            return True, csp\n",
    "\n",
    "        def solve(p, csp):\n",
    "            if p == len(csp_index):\n",
    "                return True\n",
    "            pr, pc = csp_index[p]\n",
    "            for i in csp[pr, pc]:\n",
    "                board[pr][pc] = i\n",
    "                flag, csp_temp = csp_update(pr, pc, copy.deepcopy(csp))\n",
    "                if flag:\n",
    "                    if solve(p + 1, csp_temp):\n",
    "                        return True\n",
    "                    else:\n",
    "                        board[pr][pc] = '.'\n",
    "                else:\n",
    "                    board[pr][pc] = '.'\n",
    "            return False\n",
    "\n",
    "        options = {str(x) for x in range(1, 10)}\n",
    "        csp = {}\n",
    "        csp_index = []\n",
    "        # initial csp\n",
    "        count = 0\n",
    "        for pr in range(9):\n",
    "            for pc in range(9):\n",
    "                if board[pr][pc] == '.':\n",
    "                    csp_index.append((pr, pc))\n",
    "                    csp[pr, pc] = get_csp(pr, pc)\n",
    "                    count += 1\n",
    "\n",
    "        flag = solve(0, csp)\n",
    "\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def copy(board1, board_):\n",
    "            for _i in range(9):\n",
    "                for _j in range(9):\n",
    "                    board_[_i][_j] = board1[_i][_j]\n",
    "\n",
    "        def near(i):\n",
    "            if i < 3:\n",
    "                return 0\n",
    "            if i < 6:\n",
    "                return 3\n",
    "            return 6\n",
    "\n",
    "        def square(i, j):\n",
    "            i, j = near(i), near(j)\n",
    "            ans = []\n",
    "            for a in range(i, i + 3):\n",
    "                for b in range(j, j + 3):\n",
    "                    ans.append(board[a][b])\n",
    "            return ans\n",
    "\n",
    "        def valid(arr):\n",
    "            temp = []\n",
    "            for x in arr:\n",
    "                if x not in temp:\n",
    "                    temp.append(x)\n",
    "                else:\n",
    "                    if x != '.':\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def valid_all(i, j):\n",
    "            pass\n",
    "\n",
    "        def permute(nums):\n",
    "            return list(permutations(nums, len(nums)))\n",
    "\n",
    "        def done():\n",
    "            for i in range(len(board)):\n",
    "                for j in range(len(board[0])):\n",
    "                    if board[i][j] == '.':\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def solve_one(row, column):\n",
    "            arr = ['1', '2', '3', '4', '5', '6', '7', '8', '9']\n",
    "            for i in range(9):\n",
    "                if board[row][i] in arr:\n",
    "                    arr.remove(board[row][i])\n",
    "            for i in range(9):\n",
    "                if board[i][column] in arr:\n",
    "                    arr.remove(board[i][column])\n",
    "            grid = square(row, column)\n",
    "            for i in range(9):\n",
    "                if grid[i] in arr:\n",
    "                    arr.remove(grid[i])\n",
    "            s = ''\n",
    "            for x in arr:\n",
    "                s += x\n",
    "            return s\n",
    "\n",
    "        def solve():\n",
    "            while True:\n",
    "                found = False\n",
    "                for i in range(len(board)):\n",
    "                    for j in range(len(board)):\n",
    "                        if board[i][j] == '.':\n",
    "                            elem = solve_one(i, j)\n",
    "                            if len(elem) == 1:\n",
    "                                board[i][j] = elem\n",
    "                                found = True\n",
    "                if not found:\n",
    "                    if done():\n",
    "                        return True\n",
    "                    break\n",
    "            return False\n",
    "\n",
    "        def permute_row(row):\n",
    "            arr = ['1', '2', '3', '4', '5', '6', '7', '8', '9']\n",
    "            filtered = []\n",
    "            arr2 = []\n",
    "            for i in range(9):\n",
    "                if board[row][i] in arr:\n",
    "                    arr.remove(board[row][i])\n",
    "            for i in range(9):\n",
    "                if board[row][i] == '.':\n",
    "                    elem = solve_one(row, i)\n",
    "                    arr2.append((elem, row, i))\n",
    "            perm = permute(arr)\n",
    "            for x in perm:\n",
    "                ok = True\n",
    "                for i in range(len(x)):\n",
    "                    try:\n",
    "                        arr2[i][0].index(x[i])\n",
    "                    except:\n",
    "                        ok = False\n",
    "                        break\n",
    "                if ok:\n",
    "                    filtered.append(x)\n",
    "            return filtered, arr2\n",
    "        ans = solve()\n",
    "        if ans:\n",
    "            return\n",
    "        bak = []\n",
    "        for i in range(9):\n",
    "            bak.append([0] * 9)\n",
    "        copy(board, bak)\n",
    "        for i in range(9):\n",
    "            ps, poss = permute_row(i)\n",
    "            j = 0\n",
    "            while j < len(ps):\n",
    "                p = ps[j]\n",
    "                copy(bak, board)\n",
    "                for k in range(len(p)):\n",
    "                    board[poss[k][1]][poss[k][2]] = p[k]\n",
    "                ans = solve()\n",
    "                if ans:\n",
    "                    return\n",
    "                else:\n",
    "                    j += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DLX:\n",
    "    \"\"\"\n",
    "    十字交叉双向循环链表\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, n):\n",
    "        \"\"\"\n",
    "        :param n: 数独的阶数\n",
    "        \"\"\"\n",
    "        self.n = n\n",
    "        self.m = n ** 2 * n ** 2 * 4 + 1  # 总共的列数(标注节点数+头节点)\n",
    "        self.max_nums = n ** 2 * n ** 2 * n ** 2 * 4 + self.m  # 最大节点编号\n",
    "\n",
    "        # 用下标表示节点编号，下标0表示节点0（即头节点），下标1表示节点1，以此类推...\n",
    "        self.u = [0 for _ in range(self.max_nums)]  # 记录节点的上链接点\n",
    "        self.d = [0 for _ in range(self.max_nums)]  # 记录节点的下链接点\n",
    "        self.l = [0 for _ in range(self.max_nums)]  # 记录节点的左链接点\n",
    "        self.r = [0 for _ in range(self.max_nums)]  # 记录节点的右链接点\n",
    "        self.row = [0 for _ in range(self.max_nums)]  # 记录节点所在的行\n",
    "        self.col = [0 for _ in range(self.max_nums)]  # 记录节点所在的列\n",
    "\n",
    "        # 设置首行的上下左右链接关系\n",
    "        for i in range(self.m):\n",
    "            self.u[i] = i\n",
    "            self.d[i] = i\n",
    "            self.r[i] = i + 1\n",
    "            self.l[i] = i - 1\n",
    "            self.row[i] = 0\n",
    "            self.col[i] = i\n",
    "        self.head = 0\n",
    "        self.l[self.head] = self.m - 1\n",
    "        self.r[self.m - 1] = self.head\n",
    "\n",
    "        self.s = [0 for _ in range(self.m)]  # 记录每列节点个数，以便搜索时选择节点数最少的列删除（即优化搜索方向）\n",
    "\n",
    "        self.next_point = self.m  # 下一个节点编号\n",
    "\n",
    "        self.ans = [0 for _ in range(n ** 2 * n ** 2 * n ** 2)]  # 所有答案的集合\n",
    "        self.end = 0\n",
    "\n",
    "    def add_row(self, row, columns):\n",
    "        \"\"\"\n",
    "        :param row: 新增节点所在的行\n",
    "        :param columns: 新增节点所在的列\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        first = self.next_point\n",
    "        self.l[first] = first\n",
    "        self.r[first] = first\n",
    "\n",
    "        for c in columns:\n",
    "            # 先增加新节点对上下左右节点的指向\n",
    "            self.u[self.next_point] = self.u[c]\n",
    "            self.d[self.next_point] = c\n",
    "            self.l[self.next_point] = self.l[first]\n",
    "            self.r[self.next_point] = first\n",
    "            self.row[self.next_point] = row\n",
    "            self.col[self.next_point] = c\n",
    "\n",
    "            # 然后修改上下左右节点的指向，即指向新节点\n",
    "            self.r[self.l[first]] = self.next_point\n",
    "            self.l[first] = self.next_point\n",
    "            self.d[self.u[c]] = self.next_point\n",
    "            self.u[c] = self.next_point\n",
    "\n",
    "            self.s[c] += 1  # 该列节点数+1\n",
    "\n",
    "            self.next_point += 1  # 节点编号+1\n",
    "\n",
    "    def remove(self, c):\n",
    "        \"\"\"\n",
    "        删除第c列\n",
    "        :param c:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        self.l[self.r[c]] = self.l[c]\n",
    "        self.r[self.l[c]] = self.r[c]\n",
    "\n",
    "        i = self.d[c]\n",
    "        while i != c:\n",
    "            j = self.r[i]\n",
    "            while j != i:\n",
    "                self.d[self.u[j]] = self.d[j]\n",
    "                self.u[self.d[j]] = self.u[j]\n",
    "                self.s[self.col[j]] -= 1\n",
    "                j = self.r[j]\n",
    "            i = self.d[i]\n",
    "\n",
    "    def restore(self, c):\n",
    "        \"\"\"\n",
    "        恢复第c列\n",
    "        :param c:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        i = self.u[c]\n",
    "        while i != c:\n",
    "            j = self.l[i]\n",
    "            while j != i:\n",
    "                self.d[self.u[j]] = j\n",
    "                self.u[self.d[j]] = j\n",
    "                self.s[self.col[j]] += 1\n",
    "                j = self.l[j]\n",
    "            i = self.u[i]\n",
    "        self.l[self.r[c]] = c\n",
    "        self.r[self.l[c]] = c\n",
    "\n",
    "    def dance(self, step):\n",
    "        \"\"\"\n",
    "        :param step: 递归深度\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if self.r[self.head] == self.head:\n",
    "            self.end = step\n",
    "            return True\n",
    "\n",
    "        c = self.r[self.head]\n",
    "        j = self.r[self.head]\n",
    "        # 选择节点数最少的列\n",
    "        while j != self.head:\n",
    "            if self.s[j] < self.s[c]:\n",
    "                c = j\n",
    "            j = self.r[j]\n",
    "        self.remove(c)\n",
    "\n",
    "        i = self.d[c]\n",
    "        while i != c:\n",
    "            # 删除节点i所在的行，并将其保存到结果集中\n",
    "            self.ans[step] = self.row[i]\n",
    "            j = self.r[i]\n",
    "            while j != i:\n",
    "                self.remove(self.col[j])\n",
    "                j = self.r[j]\n",
    "            if self.dance(step + 1):  # 搜索成功则返回\n",
    "                return True\n",
    "\n",
    "            # 搜索失败，要恢复，回溯\n",
    "            self.ans[step] = 0\n",
    "            j = self.l[i]\n",
    "            while j != i:\n",
    "                self.restore(self.col[j])\n",
    "                j = self.l[j]\n",
    "\n",
    "            i = self.d[i]\n",
    "        self.restore(c)\n",
    "        return False\n",
    "\n",
    "    def transform_input(self, i, j, num):\n",
    "        c1 = self.n ** 2 * (i - 1) + j\n",
    "        c2 = self.n ** 2 * self.n ** 2 + self.n ** 2 * (i - 1) + num\n",
    "        c3 = self.n ** 2 * self.n ** 2 * 2 + self.n ** 2 * (j - 1) + num\n",
    "        c4 = self.n ** 2 * self.n ** 2 * 3 + self.n ** 2 * ((i - 1) // self.n * self.n + (j - 1) // self.n) + num\n",
    "        return c1, c2, c3, c4\n",
    "\n",
    "    def run(self, input_str):\n",
    "        input_matrix = []\n",
    "        row_index = 1\n",
    "        for i in range(1, self.n ** 2 + 1):\n",
    "            for j in range(1, self.n ** 2 + 1):\n",
    "                if input_str[i - 1][j - 1] != '.':\n",
    "                    tmp = int(input_str[i - 1][j - 1])\n",
    "                    input_matrix.append((i, j, tmp))\n",
    "                    self.add_row(row_index, self.transform_input(i, j, tmp))\n",
    "                    row_index += 1\n",
    "                else:\n",
    "                    for k in range(1, self.n ** 2 + 1):\n",
    "                        input_matrix.append((i, j, k))\n",
    "                        self.add_row(row_index, self.transform_input(i, j, k))\n",
    "                        row_index += 1\n",
    "\n",
    "        if self.dance(0):\n",
    "            for i in self.ans[:self.end]:\n",
    "                input_str[input_matrix[i - 1][0] - 1][input_matrix[i - 1][1] - 1] = str(input_matrix[i - 1][2])\n",
    "        else:\n",
    "            print('Impossible')\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        dlx = DLX(3)\n",
    "        dlx.run(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "\n",
    "    def backtracking(self, board: List[List[str]]) -> bool:\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(len(board)): # 遍历行\n",
    "            for j in range(len(board[0])):  # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1, 10):  \n",
    "                    if self.is_valid(i, j, k, board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 有解\n",
    "\n",
    "    def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "        # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否有冲突\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row + 3):\n",
    "            for j in range(start_col, start_col + 3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        status = self.backtracking(board)\n",
    "        # print('main:    ', board)\n",
    "    \n",
    "    def backtracking(self, board):\n",
    "        for row in range(9):\n",
    "            for col in range(9):\n",
    "                if board[row][col] != \".\":\n",
    "                    full_status = True\n",
    "                    continue\n",
    "                \n",
    "                ans_can = [str(i) for i in range(1,10)]\n",
    "                # search row\n",
    "                for j in range(9):\n",
    "                    if board[row][j] == \".\":\n",
    "                        continue\n",
    "                    if board[row][j] in ans_can:\n",
    "                        ans_can.remove(board[row][j])\n",
    "                # search col\n",
    "                for i in range(9):\n",
    "                    if board[i][col] == \".\":\n",
    "                        continue\n",
    "                    if board[i][col] in ans_can:\n",
    "                        ans_can.remove(board[i][col])\n",
    "                # search block\n",
    "                for i in range(3 * (row // 3), 3 * (row // 3)+3):\n",
    "                    for j in range(3 * (col // 3), 3 * (col // 3)+3):\n",
    "                        if board[i][j] == \".\":\n",
    "                            continue\n",
    "                        if board[i][j] in ans_can:\n",
    "                            ans_can.remove(board[i][j])\n",
    "                if not ans_can:\n",
    "                    return False\n",
    "                # print('can: ', row, col, ans_can)\n",
    "                for ans in ans_can:\n",
    "                    board[row][col] = ans\n",
    "                    # print('ans: ', row, col, ans)\n",
    "                    status = self.backtracking(board)\n",
    "                    if status:\n",
    "                        # print('board: ', board)\n",
    "                        return status\n",
    "                    board[row][col] = \".\"\n",
    "                if not status:\n",
    "                    return False\n",
    "        if full_status:\n",
    "            # print('full_status: ', board)\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "    \n",
    "        def isValid(i,j,num):\n",
    "            for tmp_i in range(9):\n",
    "                if board[tmp_i][j]==str(num):\n",
    "                    return False\n",
    "            for tmp_j in range(9):\n",
    "                if board[i][tmp_j]==str(num):\n",
    "                    return False\n",
    "            \n",
    "            for tmp_i in range(i//3*3, i//3*3+3):\n",
    "                for tmp_j in range(j//3*3, j//3*3+3):\n",
    "                    if board[tmp_i][tmp_j]==str(num):\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def backtrace():\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if board[i][j]=='.':\n",
    "                        for num in range(1,10):\n",
    "                            if isValid(i,j,num):\n",
    "                                board[i][j]=str(num)\n",
    "                                if backtrace():\n",
    "                                    return True\n",
    "                                board[i][j]='.'\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        backtrace()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]):\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "\n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "\n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def check(x, y, value):\n",
    "            if board[x][y] != '.':\n",
    "                return False\n",
    "            if value in [i for i in board[x]]:\n",
    "                return False\n",
    "            if value in [i[y] for i in board]:\n",
    "                return False\n",
    "            around_x_start = (x//3) * 3\n",
    "            around_x_end = around_x_start+3\n",
    "            around_y_start = (y//3) * 3\n",
    "            around_y_end = around_y_start+3\n",
    "            around_values = []\n",
    "            for x_ in range(around_x_start, around_x_end):\n",
    "                for y_ in range(around_y_start, around_y_end):\n",
    "                    around_values.append(board[x_][y_])\n",
    "            if value in around_values:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        def back_tracking():\n",
    "            for x in range(0, 9):\n",
    "                for y in range(0, 9):\n",
    "                    if board[x][y] != '.':\n",
    "                        continue\n",
    "                    for value in range(1, 10):\n",
    "                        value = str(value)\n",
    "                        if check(x, y, value):\n",
    "                            board[x][y] = value\n",
    "                            state = back_tracking()\n",
    "                            if state:\n",
    "                                return True\n",
    "                            board[x][y] = '.'\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        back_tracking()\n",
    "        return\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        lst = [(i, j) for i in range(9) for j in range(9) if board[i][j] == '.']\n",
    "        se  = set(\"123456789\")\n",
    "        n   = len(lst)\n",
    "        \n",
    "        def dfs(k):            \n",
    "            if k == n: return True   \n",
    "            i, j = lst[k]\n",
    "            ii, jj = i // 3 * 3, j // 3 * 3\n",
    "            for board[i][j] in set(\"123456789\") - set(board[i]) - set(list(zip(*board))[j]) - set(board[ii][jj : jj + 3] + board[ii + 1][jj : jj + 3] + board[ii + 2][jj : jj + 3]):\n",
    "                if dfs(k + 1): return True\n",
    "            board[i][j] = '.'             \n",
    "            return False                    \n",
    "        dfs(0)                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        sudu = {str(i) for i in range(1, 10)}\n",
    "\n",
    "        def is_vaild(val, row, col):\n",
    "            # 判断同一行是否冲突\n",
    "            for i in range(9):\n",
    "                if board[row][i] == str(val):\n",
    "                    return False\n",
    "            # 判断同一列是否冲突\n",
    "            for j in range(9):\n",
    "                if board[j][col] == str(val):\n",
    "                    return False\n",
    "            # 判断同一九宫格是否有冲突\n",
    "            start_row = (row // 3) * 3\n",
    "            start_col = (col // 3) * 3\n",
    "            for i in range(start_row, start_row + 3):\n",
    "                for j in range(start_col, start_col + 3):\n",
    "                    if board[i][j] == str(val):\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def backtrack():\n",
    "            for row_inx in range(9):\n",
    "                for col_inx in range(9):\n",
    "                    if board[row_inx][col_inx] == \".\":\n",
    "                        for _su in sudu:\n",
    "                            if is_vaild(_su, row_inx, col_inx):\n",
    "                                board[row_inx][col_inx] = _su\n",
    "                                if backtrack():\n",
    "                                    return True\n",
    "                                board[row_inx][col_inx] = \".\"\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        backtrack()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "\n",
    "    def backtracking(self, board: List[List[str]]) -> bool:\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(len(board)): # 遍历行\n",
    "            for j in range(len(board[0])):  # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1, 10):\n",
    "                    if self.is_valid(i, j, k, board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 有解\n",
    "\n",
    "    def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "        # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否有冲突\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row + 3):\n",
    "            for j in range(start_col, start_col + 3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def isvalid(i, j, num):\n",
    "            if str(num) in board[i]:\n",
    "                return False\n",
    "            for x in range(0, len(board)):\n",
    "                if str(num) == board[x][j]:\n",
    "                    return False\n",
    "            for x in range(i//3*3, i//3*3+3):\n",
    "                for y in range(j//3*3, j//3*3+3):\n",
    "                    if board[x][y] == str(num):\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def backtrack():\n",
    "            for i in range(0, len(board)):\n",
    "                for j in range(0, len(board[0])):\n",
    "                    if board[i][j] == '.':\n",
    "                        for num in range(1, 10):\n",
    "                            if isvalid(i, j, num):\n",
    "                                board[i][j] = str(num)\n",
    "                                if backtrack(): return True\n",
    "                                board[i][j] = '.'\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        backtrack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "#         \"\"\"\n",
    "#         Do not return anything, modify board in-place instead.\n",
    "#         \"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "\n",
    "    def backtracking(self, board: List[List[str]]) -> bool:\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(9): # 遍历行\n",
    "            for j in range(9):  # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1, 10):\n",
    "                    if self.is_valid(i, j, k, board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 有解\n",
    "\n",
    "    def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "        # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否有冲突\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row + 3):\n",
    "            for j in range(start_col, start_col + 3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def is_valid(row,col,num_str,board):\n",
    "            # same row\n",
    "            for i in range(len(board)):\n",
    "                if board[row][i]==num_str:\n",
    "                    return False\n",
    "            # same col\n",
    "            for i in range(len(board)):\n",
    "                if board[i][col]==num_str:\n",
    "                    return False\n",
    "            # 3*3\n",
    "            row_start = 3*(row//3)\n",
    "            col_start = 3*(col//3)\n",
    "            for i in range(row_start,row_start+3):\n",
    "                for j in range(col_start,col_start+3):\n",
    "                    if board[i][j]==num_str:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def backtracking(board):\n",
    "            for i in range(len(board)):\n",
    "                for j in range(len(board)):\n",
    "                    if not board[i][j]==\".\":\n",
    "                        continue\n",
    "                    for k in range(1,10):\n",
    "                        k=str(k)\n",
    "                        if is_valid(i,j,k,board):\n",
    "                            board[i][j]=k\n",
    "                            if backtracking(board):\n",
    "                                return True\n",
    "                            board[i][j]=\".\"\n",
    "                    return False\n",
    "            return True\n",
    "        backtracking(board)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        lst, se = [(i, j) for i in range(9) for j in range(9) if board[i][j] == '.'], set(\"123456789\")\n",
    "        n = len(lst)\n",
    "        def dfs(k):            \n",
    "            if k == n: return True   \n",
    "            i, j = lst[k]\n",
    "            ii, jj = i // 3 * 3, j // 3 * 3\n",
    "            for board[i][j] in set(\"123456789\") - set(board[i]) - set(list(zip(*board))[j]) - set(board[ii][jj : jj + 3] + board[ii + 1][jj : jj + 3] + board[ii + 2][jj : jj + 3]):\n",
    "                if dfs(k + 1): return True\n",
    "            board[i][j] = '.'\n",
    "            return False  \n",
    "        dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "    def backtracking(self,board):\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j]!='.':\n",
    "                    continue\n",
    "                for k in range (1,10):\n",
    "                    if self.isValid(i,j,str(k),board):\n",
    "                        board[i][j]=str(k)\n",
    "                        if self.backtracking(board):\n",
    "                            return True\n",
    "                        board[i][j]='.'\n",
    "                return False    #1到9都没有无解\n",
    "        return True\n",
    "    def isValid(self,x,y,val,board):\n",
    "        ###按行查询\n",
    "        for i in range(len(board[0])):\n",
    "            if board[x][i]==val:\n",
    "                return False\n",
    "        ###按列查询\n",
    "        for i in range(len(board)):\n",
    "            if board[i][y]==val:\n",
    "                return False\n",
    "        ###按表格查询\n",
    "        start_row = (x//3)*3\n",
    "        start_col = (y//3)*3\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[start_row+i][start_col+j]==val:\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.dfs(board)\n",
    "    \n",
    "    def dfs(self, board) -> bool:\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == '.':\n",
    "                    for k in range(1, 10):\n",
    "                        if self.isValid(i, j, k, board):\n",
    "                            board[i][j] = str(k)\n",
    "                            if self.dfs(board):\n",
    "                                return True\n",
    "                            board[i][j] = '.'\n",
    "                    return False\n",
    "        return True\n",
    "    \n",
    "    def isValid(self, row, col, k, board):\n",
    "        for j in range(9):\n",
    "            if board[row][j] == str(k):\n",
    "                return False\n",
    "        \n",
    "        for i in range(9):\n",
    "            if board[i][col] == str(k):\n",
    "                return False\n",
    "        \n",
    "        x = (row // 3) * 3\n",
    "        y = (col // 3) * 3\n",
    "        for i in range(x, x + 3):\n",
    "            for j in range(y, y + 3):\n",
    "                if board[i][j] == str(k):\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # try1【暴力回溯】\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        # 维护每行每列每格中1-9个数字是否能进行填写（0代表能进行填写）\n",
    "        row_number = [[[0] for i in range(9)] for j in range(row)]\n",
    "        col_number = [[[0] for i in range(9)] for j in range(col)]\n",
    "        block_number = [[[0] for i in range(9)] for j in range(9)]\n",
    "\n",
    "        # 判断第i行第j列的空格能不能填写第k个数字\n",
    "        def justice(i, j, k):\n",
    "            if row_number[i][k] == 1 or col_number[j][k] == 1 or block_number[3*int(i/3) + int(j/3)][k] == 1:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        # 将存在的数字进行填入\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                # 不能进行填写的数字\n",
    "                if board[i][j] != \".\":\n",
    "                    row_number[i][int(board[i][j]) - 1] = 1\n",
    "                    col_number[j][int(board[i][j]) - 1] = 1\n",
    "                    block_number[3*int(i/3) + int(j/3)][int(board[i][j]) - 1] = 1\n",
    "\n",
    "        # 进行数字的暴力填写\n",
    "        def dfs(board):\n",
    "            for i in range(row):\n",
    "                for j in range(col):\n",
    "                    if board[i][j] == \".\":\n",
    "                        for k in range(9):  # 从1-9一一进行枚举\n",
    "                            if justice(i, j, k) == True:\n",
    "                                board[i][j] = str(k + 1)\n",
    "                                row_number[i][k] = 1\n",
    "                                col_number[j][k] = 1\n",
    "                                block_number[3 * int(i / 3) + int(j / 3)][k] = 1\n",
    "                                # 在剩下的未填写空格继续找解\n",
    "                                if (dfs(board)): return True\n",
    "                                # 找不到正确答案进行回溯\n",
    "                                board[i][j] = \".\"\n",
    "                                row_number[i][k] = 0\n",
    "                                col_number[j][k] = 0\n",
    "                                block_number[3 * int(i / 3) + int(j / 3)][k] = 0\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        dfs(board)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        self.dfs(board, 0, 0, 9)\n",
    "        return board\n",
    "    def dfs(self, board, i, j, n):\n",
    "        if i == n:\n",
    "            return True\n",
    "        if j == n:\n",
    "            return self.dfs(board, i + 1, 0, n)\n",
    "        if board[i][j] != '.':\n",
    "            return self.dfs(board, i, j + 1, n)\n",
    "        for k in range(ord('1'), ord('9') + 1):\n",
    "            ch = chr(k)\n",
    "            if not self.isValid(board, i, j, ch):\n",
    "                continue\n",
    "            board[i][j] = ch\n",
    "            if self.dfs(board, i, j + 1, n):\n",
    "                return True\n",
    "            board[i][j] = '.'\n",
    "        return False\n",
    "    def isValid(self, board, i, j, ch):\n",
    "        for k in range(9):\n",
    "            if board[i][k] == ch or board[k][j] == ch:\n",
    "                return False\n",
    "        for v in range(i // 3 * 3, i // 3 * 3 + 3):\n",
    "            for w in range(j // 3 * 3, j // 3 * 3 + 3):\n",
    "                if board[v][w] == ch:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backTracking(board)\n",
    "\n",
    "    def backTracking(self, board):\n",
    "        row, col = len(board), len(board[0])\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1,10):\n",
    "                    if self.is_valid(i, j, k, board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backTracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def is_valid(self, row, col, val, board):\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val): return False\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val): return False\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row+3):\n",
    "            for j in range(start_col, start_col+3):\n",
    "                if board[i][j] == str(val): return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Solves the Sudoku puzzle using backtracking algorithm.\n",
    "        The board is a 2D list data structure.\n",
    "        \"\"\"\n",
    "        def find_empty_location(arr, l):\n",
    "            for row in range(9):\n",
    "                for col in range(9):\n",
    "                    if arr[row][col] == \".\":\n",
    "                        l[0] = row\n",
    "                        l[1] = col\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        def used_in_row(arr, row, num):\n",
    "            for i in range(9):\n",
    "                if arr[row][i] == num:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        def used_in_col(arr, col, num):\n",
    "            for i in range(9):\n",
    "                if arr[i][col] == num:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        def used_in_box(arr, row, col, num):\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if arr[i + row][j + col] == num:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        def is_safe(arr, row, col, num):\n",
    "            return not used_in_row(arr, row, num) and not used_in_col(arr, col, num) and not used_in_box(arr, row - row % 3, col - col % 3, num)\n",
    "\n",
    "        def solve(arr):\n",
    "            l = [0, 0]\n",
    "            \n",
    "            # If there is no unassigned location, we are done\n",
    "            if not find_empty_location(arr, l):\n",
    "                return True\n",
    "            \n",
    "            # Assigning list values to row and col that we got from the above function\n",
    "            row, col = l\n",
    "\n",
    "            # Consider digits 1 to 9\n",
    "            for num in map(str, range(1, 10)):\n",
    "                # If looks promising\n",
    "                if is_safe(arr, row, col, num):\n",
    "                    # Make tentative assignment\n",
    "                    arr[row][col] = num\n",
    "\n",
    "                    # Return, if success\n",
    "                    if solve(arr):\n",
    "                        return True\n",
    "\n",
    "                    # Failure, unmake & try again\n",
    "                    arr[row][col] = \".\"\n",
    "            \n",
    "            # This triggers backtracking\n",
    "            return False\n",
    "        solve(board)\n",
    "        \n",
    "    # Utilize the backtracking algorithm to solve the sudoku\n",
    "    # if solve(board):\n",
    "    #     return board\n",
    "    # else:\n",
    "    #     return \"No solution exists\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "    def backtracking(self, board):\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                num = 1\n",
    "                if board[i][j] != '.':\n",
    "                    continue\n",
    "                for num in range(1, 10):\n",
    "                    if self.isvalid(i, j, num, board):\n",
    "                        board[i][j] = str(num)\n",
    "                        if self.backtracking(board):\n",
    "                            return True\n",
    "                        board[i][j] = '.'\n",
    "                return False\n",
    "        return True\n",
    "                    \n",
    "    def isvalid(self, row, col, val, board):\n",
    "        for i in range(9):\n",
    "            if board[i][col] == str(val):\n",
    "                return False\n",
    "\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row+3):\n",
    "            for j in range(start_col, start_col+3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "    \n",
    "    def backtracking(self,board):\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    continue\n",
    "                for k in range(1,10):\n",
    "                    if self.check_pos(i,j,k,board):\n",
    "                        board[i][j]=str(k)\n",
    "                        if self.backtracking(board):\n",
    "                            return True\n",
    "                        board[i][j]='.'\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def check_pos(self,row,col,val,board):\n",
    "        for i in range(9):\n",
    "            if board[row][i]==str(val):\n",
    "                return False\n",
    "\n",
    "        for i in range(9):\n",
    "            if board[i][col]==str(val):\n",
    "                return False\n",
    "\n",
    "        s_row=(row // 3)*3\n",
    "        s_col=(col // 3)*3\n",
    "        for i in range(s_row,s_row+3):\n",
    "            for j in range(s_col,s_col+3):\n",
    "                if board[i][j]==str(val):\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]):\n",
    "        def isValid(board, row, col, num):\n",
    "            # 判断行是否合法\n",
    "            for i in range(9):\n",
    "                if board[row][i] == num:\n",
    "                    return False\n",
    "            # 判断列是否合法\n",
    "            for i in range(9):\n",
    "                if board[i][col] == num:\n",
    "                    return False\n",
    "            # 判断3*3是否合法\n",
    "            r = row // 3 * 3\n",
    "            c = col // 3 * 3\n",
    "            for i in range(r, r + 3):\n",
    "                for j in range(c, c + 3):\n",
    "                    if board[i][j] == num:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def backtrack(board):\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if board[i][j] == '.':\n",
    "                        for num in '123456789':\n",
    "                            if isValid(board, i, j, num):\n",
    "                                board[i][j] = num\n",
    "                                if backtrack(board):\n",
    "                                    return True\n",
    "                                else:\n",
    "                                    board[i][j] = '.'  # 回溯，尝试下一个数字\n",
    "                        return False  # 所有数字都尝试完了，无解\n",
    "            return True  # 所有空格都填满了，解 Found\n",
    "        \n",
    "        backtrack(board)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def flip(i, j, x):\n",
    "            s = 1 << x\n",
    "            rows[i] ^= s \n",
    "            cols[j] ^= s\n",
    "            boxes[i//3][j//3] ^= s \n",
    "        \n",
    "        def dfs(pos):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for k in range(9):\n",
    "                s = 1 << k\n",
    "                if rows[i] & s == 0 and cols[j] & s == 0 and boxes[i//3][j//3] & s == 0:\n",
    "                    flip(i, j, k)\n",
    "                    board[i][j] = str(k + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    flip(i, j, k)\n",
    "                if valid:\n",
    "                    return \n",
    "\n",
    "        rows = [0] * 9\n",
    "        cols = [0] * 9\n",
    "        boxes = [[0] * 3 for _ in range(3)]\n",
    "        spaces = []\n",
    "        valid = False\n",
    "        for i, row in enumerate(board):\n",
    "            for j, x in enumerate(row):\n",
    "                if x == '.':\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    flip(i, j ,int(x)-1)\n",
    "        \n",
    "        dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def is_valid(board: List[List[str]], row: int, col: int, val: str) -> bool:\n",
    "            for i in range(9):\n",
    "                if board[i][col] == val or board[row][i] == val:\n",
    "                    return False\n",
    "            start_row = (row // 3) * 3\n",
    "            start_col = (col // 3) * 3\n",
    "            for r in range(start_row, start_row+3):\n",
    "                for c in range(start_col, start_col+3):\n",
    "                    if board[r][c] == val:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def backtracking(board: List[List[str]]) -> bool:   \n",
    "            for i in range(len(board)):\n",
    "                for j in range(len(board)):\n",
    "                    if board[i][j] != '.':\n",
    "                        continue\n",
    "                    for num in range(1, 10):\n",
    "                        if not is_valid(board, i, j, str(num)):\n",
    "                            continue\n",
    "                        board[i][j] = str(num)\n",
    "                        if backtracking(board):\n",
    "                            return True\n",
    "                        board[i][j] = '.'\n",
    "                    return False\n",
    "            return True\n",
    "        backtracking(board)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def backtrack(board, i, j):\n",
    "            \"\"\"i, j代表遍历到的行、列索引\"\"\"\n",
    "            if j == 9:                  # 遍历完最后一列后，转去遍历下一行\n",
    "                return backtrack(board, i+1, 0)\n",
    "            if i == 9:                  # 遍历完最后一行后，结束\n",
    "                return True\n",
    "            if board[i][j] != '.':      # 非空位置不用管\n",
    "                return backtrack(board, i, j+1)\n",
    "            for n in range(1, 10):      # 遍历选择列表，此处的选择是，给空白处填 \"1\" - \"9\" 中之一\n",
    "                c = str(n)\n",
    "                if not self.check(board, i, j, c):     # 判断选择的字符是否满足要求（不与其他位置冲突）\n",
    "                    continue\n",
    "                board[i][j] = c                 # 做出选择\n",
    "                if backtrack(board, i, j+1):    # 递归调用，直接return是因为只需要一个可行解，而不需要所有可行解\n",
    "                    return True\n",
    "                board[i][j] = '.'               # 撤销选择\n",
    "        backtrack(board, 0, 0)\n",
    "\n",
    "    def check(self, board, row, col, c):\n",
    "        for i in range(9):\n",
    "            if board[row][i] == c:\n",
    "                return False\n",
    "            if board[i][col] == c:\n",
    "                return False\n",
    "            if board[(row//3)*3 + i // 3][(col//3)*3 + i % 3] == c:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def isValid(board, i, j , str1):\n",
    "            if str1 in board[i]:\n",
    "                return False\n",
    "            for k in range(9):\n",
    "                if board[k][j] == str1:                  \n",
    "                    return False\n",
    "            p,q = i//3, j //3\n",
    "            for m in range(3):\n",
    "                for n in range(3):\n",
    "                    if board[p*3 + m][q *3 + n] == str1:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def backtrack(board,i, j):\n",
    "            if i == 8 and j == 9:\n",
    "                return True\n",
    "            if j == 9:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            \n",
    "            if board[i][j] == \".\":\n",
    "                for k in range(1,10):\n",
    "                    if isValid(board,i,j,str(k)):\n",
    "                        board[i][j] = str(k)\n",
    "                        if backtrack(board,i,j+1):\n",
    "                            return True\n",
    "                        else:\n",
    "                            board[i][j] = \".\"\n",
    "            else:\n",
    "                return backtrack(board,i,j+1)\n",
    "        \n",
    "        backtrack(board,0,0)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        row = [[False] * 9 for _ in range(9)]\n",
    "        col = [[False] * 9 for _ in range(9)]\n",
    "        cell = [[[False] * 9 for _ in range(3)] for _ in range(3)]\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    continue\n",
    "                t = int(board[i][j]) - 1\n",
    "                row[i][t] = col[j][t] = cell[i // 3][j // 3][t] = True\n",
    "\n",
    "        def dfs(board: List[List[str]], x: int, y: int) -> None:\n",
    "            if y == 9: x, y = x + 1, 0\n",
    "            if x == 9: return True\n",
    "\n",
    "            if board[x][y] != \".\":\n",
    "                return dfs(board, x, y + 1)\n",
    "            \n",
    "            for i in range(9):\n",
    "                if row[x][i] or col[y][i] or cell[x // 3][y // 3][i]:\n",
    "                    continue\n",
    "                board[x][y] = str(i + 1)\n",
    "                row[x][i] = col[y][i] = cell[x // 3][y // 3][i] = True\n",
    "                if dfs(board, x, y + 1):\n",
    "                    return True\n",
    "                board[x][y] = \".\"\n",
    "                row[x][i] = col[y][i] = cell[x // 3][y // 3][i] = False\n",
    "\n",
    "        dfs(board, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]):\n",
    "        def is_valid(board, row, col, num):\n",
    "            for i in range(9):\n",
    "                if board[row][i] == num:\n",
    "                    return False\n",
    "                if board[i][col] == num:\n",
    "                    return False\n",
    "                if board[(row//3)*3 + i//3][(col//3)*3 + i%3] == num:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def backtrack(board):\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if board[i][j] == '.':\n",
    "                        for num in range(1, 10):\n",
    "                            if is_valid(board, i, j, str(num)):\n",
    "                                board[i][j] = str(num)\n",
    "                                if backtrack(board):\n",
    "                                    return True\n",
    "                                board[i][j] = '.'\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        backtrack(board)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def isValid(board, row, col, num):\n",
    "            for i in range(9):\n",
    "                if board[row][i] == num or board[i][col] == num or board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def solve(board):\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if board[i][j] == '.':\n",
    "                        for num in map(str, range(1, 10)):\n",
    "                            if isValid(board, i, j, num):\n",
    "                                board[i][j] = num\n",
    "                                if solve(board):\n",
    "                                    return True\n",
    "                                board[i][j] = '.'\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        solve(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def dfs(pos):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "\n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        row = [[False]*9 for _ in range(9)]\n",
    "        col =[[False]*9 for _ in range(9)]\n",
    "        block =[[[False]*9 for _a in range(3)] for _b in range(3)]\n",
    "        space = []\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != \".\":\n",
    "                    index = int(board[i][j])-1\n",
    "                    row[i][index] = True\n",
    "                    col[j][index] = True\n",
    "                    block[int(i/3)][int(j/3)][index] = True\n",
    "                else:\n",
    "                    space.append((i,j))\n",
    "        valid = False\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal valid\n",
    "            if i == len(space):\n",
    "                valid = True\n",
    "                return\n",
    "            x,y = space[i]\n",
    "            for index in range(9):\n",
    "                if row[x][index] == col[y][index] == block[x//3][y//3][index] ==False:\n",
    "                    row[x][index]=col[y][index]=block[x//3][y//3][index]=True\n",
    "                    board[x][y] = str(index+1)\n",
    "                    dfs(i+1)\n",
    "                    row[x][index]=col[y][index]=block[x//3][y//3][index]=False\n",
    "                    if valid:\n",
    "                        return\n",
    "        dfs(0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def is_valid(board, row, col, num):\n",
    "            # 检查同一行是否合法\n",
    "            for i in range(9):\n",
    "                if board[row][i] == num:\n",
    "                    return False\n",
    "\n",
    "            # 检查同一列是否合法\n",
    "            for i in range(9):\n",
    "                if board[i][col] == num:\n",
    "                    return False\n",
    "\n",
    "            # 检查同一 3x3 宫内是否合法\n",
    "            start_row, start_col = 3 * (row // 3), 3 * (col // 3)\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if board[start_row + i][start_col + j] == num:\n",
    "                        return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        def solve_sudoku(board):\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if board[i][j] == '.':\n",
    "                        for num in map(str, range(1, 10)):\n",
    "                            if is_valid(board, i, j, num):\n",
    "                                board[i][j] = num\n",
    "                                if solve_sudoku(board):\n",
    "                                    return True\n",
    "                                board[i][j] = '.'  # 回溯\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        solve_sudoku(board)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board,0,0)\n",
    "    def backtracking(self,board,i,j):\n",
    "        n=len(board)\n",
    "        if i>=n:\n",
    "            return True\n",
    "        m=len(board[0])\n",
    "        if board[i][j]=='.':\n",
    "            for num in range(1,10):\n",
    "                if self.check_valid(board,i,j,num):\n",
    "                    board[i][j]=str(num)\n",
    "                    if j<m-1:\n",
    "                        if self.backtracking(board,i,j+1):\n",
    "                            return True\n",
    "                    if j==m-1:\n",
    "                        if self.backtracking(board,i+1,0):\n",
    "                            return True\n",
    "                    board[i][j]='.'\n",
    "            return False\n",
    "        else:\n",
    "            if j<m-1:\n",
    "                if self.backtracking(board,i,j+1):\n",
    "                    return True\n",
    "            if j==m-1:\n",
    "                if self.backtracking(board,i+1,0):\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "    def check_valid(self,board,i,j,number):\n",
    "        for c in range(9):  #检查列\n",
    "            if board[c][j]==str(number):\n",
    "                return False\n",
    "        for l in range(9):  #检查行\n",
    "            if board[i][l]==str(number):\n",
    "                return False\n",
    "        c=(i//3)*3\n",
    "        l=(j//3)*3\n",
    "        for x in range(c,c+3):  #检查九宫格\n",
    "            for y in range(l,l+3):\n",
    "                if board[x][y]==str(number):\n",
    "                    return False\n",
    "        return True \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "\n",
    "    def backtracking(self, board: List[List[str]]) -> bool:\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(len(board)): # 遍历行\n",
    "            for j in range(len(board[0])):  # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1, 10):\n",
    "                    if self.is_valid(i, j, k, board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 有解\n",
    "\n",
    "    def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "        # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否有冲突\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row + 3):\n",
    "            for j in range(start_col, start_col + 3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.n = len(board)\n",
    "        self.board = board\n",
    "        self.cols = [0] * self.n\n",
    "        self.rows = [0] * self.n\n",
    "        self.block = [[0 for i in range(self.n//3)] for j in range(self.n//3)]\n",
    "        self.get_bitset()\n",
    "        self.dfs()\n",
    "    \n",
    "    def get_bitset(self):\n",
    "        for i in range(self.n):\n",
    "            for j in range(self.n):\n",
    "                val = self.board[i][j]\n",
    "                if val == '.':\n",
    "                    continue\n",
    "                val_ord = ord(val) - ord('0') - 1\n",
    "                self.cols[j] += 1 << val_ord\n",
    "                self.rows[i] += 1 << val_ord\n",
    "                self.block[i//3][j//3] += 1 << val_ord\n",
    "    \n",
    "    def get_possible_status(self, row, col):\n",
    "        bit = ~(self.cols[col] | self.rows[row] | self.block[row//3][col//3])\n",
    "        return bit\n",
    "    \n",
    "    def get_next(self):\n",
    "        c_min = 10\n",
    "        c_pos = None\n",
    "        \n",
    "        for i in range(self.n):\n",
    "            for j in range(self.n):\n",
    "                c = 0\n",
    "                if self.board[i][j] == \".\":\n",
    "                    num = self.get_possible_status(i, j)\n",
    "                    for k in range(self.n):\n",
    "                        if num >> k & 1 == 1:\n",
    "                            c += 1\n",
    "                    if c < c_min:\n",
    "                        c_min = c\n",
    "                        c_pos = (i, j)\n",
    "        return c_pos\n",
    "    \n",
    "    def dfs(self):\n",
    "        next = self.get_next()\n",
    "        if next is None:\n",
    "            return True\n",
    "        (row, col) = next\n",
    "        bit_num = self.get_possible_status(row, col)\n",
    "            \n",
    "        for i in range(self.n):\n",
    "            if bit_num >> i & 1== 1:\n",
    "                self.board[row][col] = str(i+1)\n",
    "                self.fill_num(row, col, str(i+1), 'add')\n",
    "                if self.dfs():\n",
    "                    return True\n",
    "                self.fill_num(row, col, str(i+1), 'delete')\n",
    "                self.board[row][col] = '.'\n",
    "        return False\n",
    "                    \n",
    "    \n",
    "    def fill_num(self, row, col, num, opt):\n",
    "        val = self.board[row][col]\n",
    "        val_ord = ord(val) - ord('0') - 1\n",
    "        if opt == \"add\":\n",
    "            self.cols[col] += 1 << val_ord\n",
    "            self.rows[row] += 1 << val_ord\n",
    "            self.block[row//3][col//3] += 1 << val_ord\n",
    "        else:\n",
    "            self.cols[col] -= 1 << val_ord\n",
    "            self.rows[row] -= 1 << val_ord\n",
    "            self.block[row//3][col//3] -= 1 << val_ord\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_valid(self, row: int, col: int, val: int, board):\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "        # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否有冲突\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row + 3):\n",
    "            for j in range(start_col, start_col + 3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def solveSudoku(self, board):\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def back(state):\n",
    "            for row in range(len(board)):\n",
    "                for col in range(len(board[0])):\n",
    "                    if board[row][col] != '.':\n",
    "                        continue\n",
    "                    for k in range(1, 10):\n",
    "                        if self.is_valid(row, col, k, state):\n",
    "                            state[row][col] = str(k)\n",
    "                            if back(state):\n",
    "                                return True\n",
    "                            state[row][col] = \".\"\n",
    "                    return False\n",
    "            return True\n",
    "        back(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        columns = [[0 for _ in range(9)] for _ in range(9)]\n",
    "        rows = [[0 for _ in range(9)] for _ in range(9)]\n",
    "        grids = [[[0 for _ in range(9)] for _ in range(3)] for _ in range(3)]\n",
    "\n",
    "\n",
    "        sublist = []\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == '.':\n",
    "                    sublist.append((i,j))\n",
    "                else:\n",
    "                    num = int(board[i][j]) -1 \n",
    "                    columns[i][num] += 1 \n",
    "                    rows[j][num] += 1 \n",
    "                    grids[i//3][j//3][num] += 1 \n",
    "        valid = False\n",
    "        def dfs(path,idx):\n",
    "            nonlocal valid\n",
    "            if idx == len(path):\n",
    "                valid = True \n",
    "                return \n",
    "            i,j = path[idx]\n",
    "            for k in range(9):\n",
    "                if columns[i][k]==0 and rows[j][k] == 0 and grids[i//3][j//3][k] == 0:\n",
    "                    board[i][j] = str(k+1)\n",
    "                    columns[i][k] += 1 \n",
    "                    rows[j][k] += 1 \n",
    "                    grids[i//3][j//3][k] += 1 \n",
    "                    dfs(path,idx+1)\n",
    "              \n",
    "                    columns[i][k] -= 1 \n",
    "                    rows[j][k] -= 1 \n",
    "                    grids[i//3][j//3][k] -= 1 \n",
    "                \n",
    "                if valid:\n",
    "                    break\n",
    "        dfs(sublist,0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        self.back(board)\n",
    "        return board\n",
    "\n",
    "    def back(self, board):\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(len(board)): # 遍历行\n",
    "            for j in range(len(board[0])):  # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1, 10):\n",
    "                    if self.islegitimate(board, i, j, str(k)):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.back(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 有解\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def islegitimate(self, board, y, x, value):\n",
    "\n",
    "        for i in range(9):\n",
    "            if board[y][i] == value or board[i][x] == value:\n",
    "                return False\n",
    "\n",
    "        start_x = (x // 3) * 3\n",
    "        start_y = (y // 3) * 3\n",
    "        for i in range(start_x, start_x + 3):\n",
    "            for j in range(start_y, start_y + 3):\n",
    "                if board[j][i] == value:\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board,0,0)\n",
    "    def backtracking(self,board,i,j):\n",
    "        n=len(board)\n",
    "        if i>=n:\n",
    "            return True\n",
    "        m=len(board[0])\n",
    "        if board[i][j]=='.':\n",
    "            for num in range(1,10):\n",
    "                if self.check_valid(board,i,j,num):\n",
    "                    board[i][j]=str(num)\n",
    "                    if j<m-1:\n",
    "                        if self.backtracking(board,i,j+1):\n",
    "                            return True\n",
    "                    if j==m-1:\n",
    "                        if self.backtracking(board,i+1,0):\n",
    "                            return True\n",
    "                    board[i][j]='.'\n",
    "            return False\n",
    "        else:\n",
    "            if j<m-1:\n",
    "                if self.backtracking(board,i,j+1):\n",
    "                    return True\n",
    "            if j==m-1:\n",
    "                if self.backtracking(board,i+1,0):\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "    def check_valid(self,board,i,j,number):\n",
    "        for c in range(9):  #检查列\n",
    "            if board[c][j]==str(number):\n",
    "                return False\n",
    "        for l in range(9):  #检查行\n",
    "            if board[i][l]==str(number):\n",
    "                return False\n",
    "        c=(i//3)*3\n",
    "        l=(j//3)*3\n",
    "        for x in range(c,c+3):  #检查九宫格\n",
    "            for y in range(l,l+3):\n",
    "                if board[x][y]==str(number):\n",
    "                    return False\n",
    "        return True \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 判断是否在行、列、小方格出现\n",
    "        row = [[False] * 9 for _ in range(9)]\n",
    "        col = [[False] * 9 for _ in range(9)]\n",
    "        cell = [[[False] * 9 for _ in range(3)] for _ in range(3)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    t = ord(board[i][j]) - ord('1')\n",
    "                    row[i][t] = True\n",
    "                    col[j][t] = True\n",
    "                    cell[i // 3][j // 3][t] = True\n",
    "        def dfs(board, x, y):\n",
    "            # 列走到末尾则换行\n",
    "            if y == 9:\n",
    "                y = 0\n",
    "                x += 1\n",
    "            if x == 9:\n",
    "                return True\n",
    "            \n",
    "            # 不需要填数字\n",
    "            if board[x][y] != '.':\n",
    "                return dfs(board, x, y + 1)\n",
    "            \n",
    "            # 枚举(x,y)要填的数字\n",
    "            for t in range(1, 10):\n",
    "                if not row[x][t - 1] and not col[y][t - 1] and not cell[x // 3][y // 3][t - 1]:\n",
    "                    board[x][y] = str(t)\n",
    "                    row[x][t - 1] = True\n",
    "                    col[y][t - 1] = True\n",
    "                    cell[x // 3][y // 3][t - 1] = True\n",
    "\n",
    "                    if dfs(board, x, y + 1):\n",
    "                        return True\n",
    "                    \n",
    "                    # 恢复现场\n",
    "                    board[x][y] = '.'\n",
    "                    row[x][t - 1] = False\n",
    "                    col[y][t - 1] = False\n",
    "                    cell[x // 3][y // 3][t - 1] = False\n",
    "            \n",
    "            # 1 ~ 9都填不了\n",
    "            return False\n",
    "        \n",
    "        dfs(board, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        nums = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}\n",
    "        row = [set() for _ in range(9)]\n",
    "        column = [set() for _ in range(9)]\n",
    "        table = [[set() for _ in range(3)] for _ in range(3)]\n",
    "        empty = []\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                num = board[i][j]\n",
    "                if num == \".\":\n",
    "                    empty.append((i, j))\n",
    "                else:\n",
    "                    row[i].add(num)\n",
    "                    column[j].add(num)\n",
    "                    table[i//3][j//3].add(num)\n",
    "\n",
    "        def dfs(n):\n",
    "            if n == len(empty): return True\n",
    "            i, j = empty[n]\n",
    "            choice = nums - row[i] - column[j] - table[i//3][j//3]\n",
    "            for num in choice:\n",
    "                \n",
    "                row[i].add(num)\n",
    "                column[j].add(num)\n",
    "                table[i//3][j//3].add(num)\n",
    "                if dfs(n + 1): \n",
    "                    board[i][j] = num\n",
    "                    return True\n",
    "                row[i].remove(num)\n",
    "                column[j].remove(num)\n",
    "                table[i//3][j//3].remove(num)\n",
    "\n",
    "        dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        self.backtracking(board)\n",
    "    \n",
    "\n",
    "    def backtracking(self,board:List[List[str]]) -> bool:\n",
    "        # 如果有解，返回True;如果没有解，返回False\n",
    "        for i in range(len(board)): # 遍历行\n",
    "            for j in range(len(board[0])): # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.':continue\n",
    "                for k in range(1,10):\n",
    "                    if self.isValid(i,j,k,board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若1到9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 上面都执行完了，没有遇到False的情况，证明有解\n",
    "    \n",
    "\n",
    "    def isValid(self,row:int,col:int,val:int,board:List[List[str]]) -> bool:\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "            # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否冲突：\n",
    "        start_row = (row//3) *3\n",
    "        start_col = (col//3) *3\n",
    "        for i in range(start_row,start_row+3):\n",
    "            for j in range(start_col,start_col+3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, grid: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        board = copy.deepcopy(grid)\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    board[i][j] = 0\n",
    "                else:\n",
    "                    board[i][j] = int(board[i][j])\n",
    "\n",
    "        def find_empty(board : List[List[str]]):\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if board[i][j] == 0:\n",
    "                        return (i,j)\n",
    "\n",
    "            return None\n",
    "\n",
    "        # is_valid() 判断 (row,col) 的格子中填 num 满不满足条件\n",
    "        def is_valid(num, row, col):\n",
    "            for i in range(9):\n",
    "                if board[row][i] == num or board[i][col] == num:\n",
    "                    return False\n",
    "            start_row, start_col = 3 * (row // 3), 3 * (col // 3)\n",
    "            for i in range(start_row, start_row + 3):\n",
    "                for j in range(start_col, start_col + 3):\n",
    "                    if board[i][j] == num:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        def dfs() -> bool:\n",
    "            p = find_empty(board)\n",
    "            i,j = -1,-1\n",
    "            if p != None:\n",
    "                i,j = p\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "            # print(p)\n",
    "\n",
    "            for x in range(1,10):\n",
    "                # board[i][j] = x\n",
    "                # print(i,j,x)\n",
    "\n",
    "                if is_valid(x,i,j):\n",
    "                    board[i][j] = x\n",
    "\n",
    "                    if dfs():\n",
    "                        return True\n",
    "                    else:\n",
    "                        board[i][j] = 0\n",
    "                    \n",
    "\n",
    "            return False\n",
    "                    \n",
    "        \n",
    "        dfs()\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if grid[i][j] == '.':\n",
    "                    grid[i][j] = str(board[i][j])\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        row = [[0]*9 for _ in range(9)]\n",
    "        col = [[0]*9 for _ in range(9)]\n",
    "        box = [[0]*9 for _ in range(9)]\n",
    "\n",
    "        def is_valid(i, j, num):\n",
    "            if row[i][num] == 1:\n",
    "                return False\n",
    "            if col[j][num] == 1:\n",
    "                return False\n",
    "            idx = i//3*3+j//3\n",
    "            if box[idx][num] == 1:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        space = []\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != \".\":\n",
    "                    num = int(board[i][j])-1\n",
    "                    row[i][num] = 1\n",
    "                    col[j][num] = 1\n",
    "                    box[i // 3 * 3 + j // 3][num] = 1\n",
    "                else:\n",
    "                    space.append([i,j])\n",
    "\n",
    "        def backtrack(index):\n",
    "            if index == len(space):\n",
    "                return True\n",
    "            i ,j = space[index]\n",
    "            for n in range(9):\n",
    "                if is_valid(i, j, n):\n",
    "                    board[i][j] = str(n+1)\n",
    "                    row[i][n] = 1\n",
    "                    col[j][n] = 1\n",
    "                    box[i // 3 * 3 + j // 3][n] = 1\n",
    "                    if backtrack(index+1):\n",
    "                        return True\n",
    "                    board[i][j] = \".\"\n",
    "                    row[i][n] = 0\n",
    "                    col[j][n] = 0\n",
    "                    box[i // 3 * 3 + j // 3][n] = 0\n",
    "            return False\n",
    "\n",
    "        backtrack(0)\n",
    "                        \n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        return self.backtrack(board, 0, 0)\n",
    "    def backtrack(self,board:List[List[str]], i:int,j:int) ->None:\n",
    "        m, n = 9, 9\n",
    "        if j == n:\n",
    "            return self.backtrack(board, i+1, 0)\n",
    "        if i == m:\n",
    "            return True\n",
    "        if board[i][j] != '.':\n",
    "            return  self.backtrack(board, i, j+1)\n",
    "        for ch in range(ord('1'),ord('9')+1):\n",
    "            ch = chr(ch)\n",
    "            if not self.isValid(board, i, j, ch):\n",
    "                continue\n",
    "            board[i][j] = ch\n",
    "            if self.backtrack(board, i, j+1):\n",
    "                return True\n",
    "            board[i][j] = '.'\n",
    "        return False    \n",
    "    def isValid(self,board:List[List[str]], r:int,c:int,n:int) ->bool:\n",
    "        for i in range(9):\n",
    "            if board[r][i] == n:\n",
    "                return False\n",
    "            if board[i][c] == n:\n",
    "                return False\n",
    "            if board[(r//3)*3+i//3][(c//3)*3+i%3] == n:\n",
    "                return False\n",
    "        return True    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "\n",
    "    def backtracking(self, board: List[List[str]]) -> bool:\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(len(board)): # 遍历行\n",
    "            for j in range(len(board[0])):  # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1, 10):\n",
    "                    if self.is_valid(i, j, k, board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 有解\n",
    "\n",
    "    def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "        # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否有冲突\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row + 3):\n",
    "            for j in range(start_col, start_col + 3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        nums = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}\n",
    "        row = [set() for _ in range(9)]\n",
    "        column = [set() for _ in range(9)]\n",
    "        table = [[set() for _ in range(3)] for _ in range(3)]\n",
    "        empty = []\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                num = board[i][j]\n",
    "                if num == \".\":\n",
    "                    empty.append((i, j))\n",
    "                else:\n",
    "                    row[i].add(num)\n",
    "                    column[j].add(num)\n",
    "                    table[i//3][j//3].add(num)\n",
    "\n",
    "        def dfs(n):\n",
    "            if n == len(empty): return True\n",
    "            i, j = empty[n]\n",
    "            choice = nums - row[i] - column[j] - table[i//3][j//3]\n",
    "            for num in choice:\n",
    "                \n",
    "                row[i].add(num)\n",
    "                column[j].add(num)\n",
    "                table[i//3][j//3].add(num)\n",
    "                if dfs(n + 1): \n",
    "                    board[i][j] = num\n",
    "                    return True\n",
    "                row[i].remove(num)\n",
    "                column[j].remove(num)\n",
    "                table[i//3][j//3].remove(num)\n",
    "\n",
    "        dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        self.back(board)\n",
    "        return board\n",
    "\n",
    "\n",
    "    def back(self, board):\n",
    "\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(9): # 遍历行\n",
    "            for j in range(9):  # 遍历列\n",
    "\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': \n",
    "                    continue\n",
    "\n",
    "                for k in range(1, 10):\n",
    "                    if self.islegitimate(board, i, j, str(k)):\n",
    "                        board[i][j] = str(k)\n",
    "                        \n",
    "                        find = self.back(board)\n",
    "                        \n",
    "                        if find == True: \n",
    "                            return True\n",
    "\n",
    "                        board[i][j] = '.'\n",
    "\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "\n",
    "        return True # 有解\n",
    "\n",
    "\n",
    "\n",
    "    def islegitimate(self, board, y, x, value):\n",
    "\n",
    "        for i in range(9):\n",
    "            if board[y][i] == value or board[i][x] == value:\n",
    "                return False\n",
    "\n",
    "        start_x = (x // 3) * 3\n",
    "        start_y = (y // 3) * 3\n",
    "        for i in range(start_x, start_x + 3):\n",
    "            for j in range(start_y, start_y + 3):\n",
    "                if board[j][i] == value:\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(81):\n",
    "            if board[i//9][i % 9] == '.':\n",
    "                for j in range(9):\n",
    "                    if self.ifok(board, j+1, [i//9, i % 9]):\n",
    "                        # b2 = copy.deepcopy(board)\n",
    "                        # b2[i//9][i % 9] = str(j+1)\n",
    "                        # elseok = self.solveSudoku(b2)\n",
    "                        board[i//9][i % 9] = str(j+1)\n",
    "                        elseok = self.solveSudoku(board)\n",
    "                        if not elseok:\n",
    "                            board[i//9][i % 9] = '.'\n",
    "                            continue\n",
    "                        else:\n",
    "                            return True\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def ifok(self, board, n, place):\n",
    "        for i in range(9):\n",
    "            if board[place[0]][i] != '.' and int(board[place[0]][i]) == n:\n",
    "                return False\n",
    "        for i in range(9):\n",
    "            if board[i][place[1]] != '.' and int(board[i][place[1]]) == n:\n",
    "                return False\n",
    "        block = []\n",
    "        block.append(place[0]//3*3)\n",
    "        block.append(place[1]//3*3)\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if board[block[0]+i][block[1]+j] != '.' and int(board[block[0]+i][block[1]+j]) == n:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        n = len(board)\n",
    "        row_memo = [[False] * n for _ in range(n)] \n",
    "        col_memo = [[False] * n for _ in range(n)] \n",
    "        block = [[[False] * n for _ in range(n//3)] for _ in range(n//3)]\n",
    "        space = []\n",
    "        valid = False\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (board[i][j] == \".\"):\n",
    "                    space.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    row_memo[i][digit] = True\n",
    "                    col_memo[j][digit] = True\n",
    "                    block[i//3][j//3][digit] = True\n",
    "        \n",
    "        def backtrack(index):\n",
    "            nonlocal valid\n",
    "            if (index == len(space)):\n",
    "                valid = True\n",
    "                return              \n",
    "            (i, j) = space[index]\n",
    "            for k in range(1, 10):\n",
    "                if (valid == True):\n",
    "                    return\n",
    "                if (row_memo[i][k-1] == False and col_memo[j][k-1] == False and block[i//3][j//3][k-1] == False):\n",
    "                    row_memo[i][k-1] = True\n",
    "                    col_memo[j][k-1] = True\n",
    "                    block[i//3][j//3][k-1] = True\n",
    "                    board[i][j] = str(k)\n",
    "                    backtrack(index+1)\n",
    "                    row_memo[i][k-1] = False\n",
    "                    col_memo[j][k-1] = False\n",
    "                    block[i//3][j//3][k-1] = False\n",
    "\n",
    "        backtrack(0)\n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        \n",
    "        self.rows = [set() for _ in range(9)]\n",
    "        self.columns = [set() for _ in range(9)]\n",
    "        self.subboxes = [[set() for _ in range(9)] for _ in range(3)]\n",
    "    \n",
    "    def isValidSudoku(self, board, row, col, num):\n",
    "        if num in self.rows[row] or num in self.columns[col] or num in self.subboxes[row//3][col//3]:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def solveSudoku(self, board):\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] != '.':\n",
    "                    self.rows[i].add(board[i][j])\n",
    "                    self.columns[j].add(board[i][j])\n",
    "                    self.subboxes[i//3][j//3].add(board[i][j])\n",
    "        \n",
    "        self._solve(board)\n",
    "\n",
    "    def _solve(self, board):\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == '.':\n",
    "                    for num in map(str, range(1,10)):\n",
    "                        if self.isValidSudoku(board, i, j, num):\n",
    "                            board[i][j] = num\n",
    "                            self.rows[i].add(num)\n",
    "                            self.columns[j].add(num)\n",
    "                            self.subboxes[i//3][j//3].add(num)\n",
    "\n",
    "                            if self._solve(board):\n",
    "                                return True\n",
    "\n",
    "                            board[i][j] = '.'\n",
    "                            self.rows[i].remove(num)\n",
    "                            self.columns[j].remove(num)\n",
    "                            self.subboxes[i//3][j//3].remove(num)\n",
    "                    return False\n",
    "\n",
    "        return True\n",
    "\n",
    "                        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(board)\n",
    "        row_memo = [[False] * n for _ in range(n)] \n",
    "        col_memo = [[False] * n for _ in range(n)] \n",
    "        block = [[[False] * n for _ in range(n//3)] for _ in range(n//3)]\n",
    "        space = []\n",
    "        valid = False\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (board[i][j] == \".\"):\n",
    "                    space.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    row_memo[i][digit] = True\n",
    "                    col_memo[j][digit] = True\n",
    "                    block[i//3][j//3][digit] = True\n",
    "        \n",
    "        def backtrack(index):\n",
    "            nonlocal valid\n",
    "            if (index == len(space)):\n",
    "                valid = True\n",
    "                return              \n",
    "            (i, j) = space[index]\n",
    "            for k in range(1, 10):\n",
    "                if (valid == True):\n",
    "                    return\n",
    "                if (row_memo[i][k-1] == False and col_memo[j][k-1] == False and block[i//3][j//3][k-1] == False):\n",
    "                    row_memo[i][k-1] = True\n",
    "                    col_memo[j][k-1] = True\n",
    "                    block[i//3][j//3][k-1] = True\n",
    "                    board[i][j] = str(k)\n",
    "                    backtrack(index+1)\n",
    "                    row_memo[i][k-1] = False\n",
    "                    col_memo[j][k-1] = False\n",
    "                    block[i//3][j//3][k-1] = False\n",
    "\n",
    "        backtrack(0)\n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9): #遍历题目\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\r\n",
    "        \"\"\"\r\n",
    "        Do not return anything, modify board in-place instead.\r\n",
    "        \"\"\"\r\n",
    "        self.backtrack(board, 0, 0)\r\n",
    "\r\n",
    "    def backtrack(self, board, row, col):\r\n",
    "        n = len(board)\r\n",
    "        if col == n:\r\n",
    "            return self.backtrack(board, row + 1, 0)\r\n",
    "        if row == n:\r\n",
    "            return True\r\n",
    "\r\n",
    "        if board[row][col] != '.':\r\n",
    "            # 预设数字，跳过\r\n",
    "            return self.backtrack(board, row, col + 1)\r\n",
    "    \r\n",
    "        for num in range(1, 10):\r\n",
    "            num = str(num)\r\n",
    "            # 不合法数字，跳过\r\n",
    "            if not self.isValid(board, row, col, num):\r\n",
    "                continue\r\n",
    "            # 可行解，填入\r\n",
    "            board[row][col] = num\r\n",
    "            if self.backtrack(board, row, col + 1):\r\n",
    "                return True\r\n",
    "            # 还原\r\n",
    "            board[row][col] = '.' \r\n",
    "        return False\r\n",
    "    \r\n",
    "    def isValid(self, board, r, c, num):\r\n",
    "        n = len(board)\r\n",
    "        # num = board[r][c]\r\n",
    "        # 检查行\r\n",
    "        for i in range(n):\r\n",
    "            if num == board[r][i] and i != c:\r\n",
    "            # if num == board[r][i]:\r\n",
    "                return False\r\n",
    "        # 检查列\r\n",
    "        for j in range(n):\r\n",
    "            if num == board[j][c] and j != r:\r\n",
    "            # if num == board[j][c]:\r\n",
    "                return False\r\n",
    "        # 检查九宫格\r\n",
    "        for i in range((r // 3) * 3, (r // 3) * 3 + 3):\r\n",
    "            for j in range((c // 3) * 3, (c // 3) * 3 + 3):\r\n",
    "                if num == board[i][j] and (i != r or j != c):\r\n",
    "                    return False\r\n",
    "        \r\n",
    "        # start_row, start_col = (r // 3) * 3, (c // 3) * 3\r\n",
    "        # for i in range(start_row, start_row + 3):\r\n",
    "        #     for j in range(start_col, start_col + 3):\r\n",
    "        #         if (i != r or j != c) and board[i][j] == num:\r\n",
    "        #             return False\r\n",
    "        \r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        nums = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}\n",
    "        row = [set() for _ in range(9)]\n",
    "        column = [set() for _ in range(9)]\n",
    "        table = [[set() for _ in range(3)] for _ in range(3)]\n",
    "        empty = []\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                num = board[i][j]\n",
    "                if num == \".\":\n",
    "                    empty.append((i, j))\n",
    "                else:\n",
    "                    row[i].add(num)\n",
    "                    column[j].add(num)\n",
    "                    table[i//3][j//3].add(num)\n",
    "\n",
    "        def dfs(n):\n",
    "            if n == len(empty): return True\n",
    "            i, j = empty[n]\n",
    "            choice = nums - row[i] - column[j] - table[i//3][j//3]\n",
    "            for num in choice:\n",
    "                board[i][j] = num\n",
    "                row[i].add(num)\n",
    "                column[j].add(num)\n",
    "                table[i//3][j//3].add(num)\n",
    "                if dfs(n + 1): \n",
    "                    return True\n",
    "                row[i].remove(num)\n",
    "                column[j].remove(num)\n",
    "                table[i//3][j//3].remove(num)\n",
    "\n",
    "        dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "\n",
    "    def backtracking(self, board: List[List[str]]) -> bool:\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(len(board)): # 遍历行\n",
    "            for j in range(len(board[0])):  # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1, 10):  \n",
    "                    if self.is_valid(i, j, k, board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 有解\n",
    "\n",
    "    def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "        # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否有冲突\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row + 3):\n",
    "            for j in range(start_col, start_col + 3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.backtracking(board)\n",
    "\n",
    "    def backtracking(self, board: List[List[str]]) -> bool:\n",
    "        # 若有解，返回True；若无解，返回False\n",
    "        for i in range(len(board)): # 遍历行\n",
    "            for j in range(len(board[0])):  # 遍历列\n",
    "                # 若空格内已有数字，跳过\n",
    "                if board[i][j] != '.': continue\n",
    "                for k in range(1, 10):  \n",
    "                    if self.is_valid(i, j, k, board):\n",
    "                        board[i][j] = str(k)\n",
    "                        if self.backtracking(board): return True\n",
    "                        board[i][j] = '.'\n",
    "                # 若数字1-9都不能成功填入空格，返回False无解\n",
    "                return False\n",
    "        return True # 有解\n",
    "\n",
    "    def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:\n",
    "        # 判断同一行是否冲突\n",
    "        for i in range(9):\n",
    "            if board[row][i] == str(val):\n",
    "                return False\n",
    "        # 判断同一列是否冲突\n",
    "        for j in range(9):\n",
    "            if board[j][col] == str(val):\n",
    "                return False\n",
    "        # 判断同一九宫格是否有冲突\n",
    "        start_row = (row // 3) * 3\n",
    "        start_col = (col // 3) * 3\n",
    "        for i in range(start_row, start_row + 3):\n",
    "            for j in range(start_col, start_col + 3):\n",
    "                if board[i][j] == str(val):\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        choice_pool = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}\n",
    "        row = [set() for _ in range(9)]\n",
    "        column = [set() for _ in range(9)]\n",
    "        table = [[set() for _ in range(3)] for _ in range(3)]\n",
    "        to_be_filled = []\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                num = board[i][j]\n",
    "                if num == \".\":\n",
    "                    to_be_filled.append((i, j))\n",
    "                else:\n",
    "                    row[i].add(num)\n",
    "                    column[j].add(num)\n",
    "                    table[i//3][j//3].add(num)\n",
    "\n",
    "        def deepest_first_search(n):\n",
    "            if n == len(to_be_filled): return True\n",
    "            i, j = to_be_filled[n]\n",
    "            choice = choice_pool - row[i] - column[j] - table[i//3][j//3]\n",
    "            for num in choice:\n",
    "                row[i].add(num)\n",
    "                column[j].add(num)\n",
    "                table[i//3][j//3].add(num)\n",
    "                if deepest_first_search(n + 1): \n",
    "                    board[i][j] = num\n",
    "                    return True\n",
    "                row[i].remove(num)\n",
    "                column[j].remove(num)\n",
    "                table[i//3][j//3].remove(num)\n",
    "\n",
    "        deepest_first_search(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def possiblenum(i,j):\n",
    "            t=~(row[i]|col[j]|box[i//3][j//3])\n",
    "            return [i for i in range(9) if t&(1<<i)]\n",
    "        def getnext():\n",
    "            minn=10\n",
    "            a,b=0,0\n",
    "            for i in range(9):\n",
    "                for j in range(9):\n",
    "                    if(board[i][j]=='.'):\n",
    "                        t=possiblenum(i,j)\n",
    "                        n=len(t)\n",
    "                        if(n==1):\n",
    "                            return i,j\n",
    "                        elif(n<minn):\n",
    "                            a=i\n",
    "                            b=j\n",
    "                            minn=n\n",
    "            return a,b        \n",
    "        def fix_board(i,j,k,b):\n",
    "            if(b<0):\n",
    "                board[i][j]='.'\n",
    "                row[i]&=~(1<<(k))\n",
    "                col[j]&=~(1<<(k))\n",
    "                box[i//3][j//3]&=~(1<<(k))\n",
    "            else:\n",
    "                board[i][j]=str(k+1)\n",
    "                row[i]|=(1<<k)\n",
    "                col[j]|=(1<<k)\n",
    "                box[i//3][j//3]|=(1<<k)\n",
    "\n",
    "\n",
    "        def dfs(num):\n",
    "            if(num==0):\n",
    "                return True\n",
    "            i,j=getnext()\n",
    "            p=possiblenum(i,j)\n",
    "            for k in p:\n",
    "                fix_board(i,j,k,1)\n",
    "                if(dfs(num-1)):\n",
    "                    return True\n",
    "                fix_board(i,j,k,-1)\n",
    "            return False\n",
    "        row=[0 for i in range(9)]\n",
    "        col=[0 for i in range(9)]\n",
    "        box=[[0 for i in range(3)]for j in range(3)]\n",
    "        num=0\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if(board[i][j]=='.'):\n",
    "                    num+=1\n",
    "                else:\n",
    "                    p=int(board[i][j])-1\n",
    "                    row[i]|=(1<<p)\n",
    "                    col[j]|=(1<<p)\n",
    "                    box[i//3][j//3]|=(1<<p)\n",
    "        dfs(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 初始化行、列和宫的集合\n",
    "        lines = [set() for _ in range(9)]\n",
    "        cols = [set() for _ in range(9)]\n",
    "        sqs = [set() for _ in range(9)]\n",
    "        empty_list = []  # 存储空格位置的列表\n",
    "\n",
    "        # 遍历数独棋盘，初始化集合和空格列表\n",
    "        for i, line in enumerate(board):\n",
    "            for j, ch in enumerate(line):\n",
    "                if ch == '.':\n",
    "                    empty_list.append((i, j))\n",
    "                else:\n",
    "                    lines[i].add(ch)\n",
    "                    cols[j].add(ch)\n",
    "                    sqs[(i // 3) * 3 + (j // 3)].add(ch)\n",
    "\n",
    "        res = []  # 存储填充结果的列表\n",
    "\n",
    "        def dfs(k):\n",
    "            # 递归终止条件：如果所有空格都填充完毕，返回True\n",
    "            if k == len(empty_list):\n",
    "                return True\n",
    "\n",
    "            i, j = empty_list[k]\n",
    "\n",
    "            # 尝试填入数字'1'到'9'\n",
    "            for ch in '123456789':\n",
    "                if not (ch in lines[i] or ch in cols[j] or ch in sqs[(i // 3) * 3 + (j // 3)]):\n",
    "                    # 如果数字在当前行、列、宫中均不存在，填入并更新相关集合\n",
    "                    lines[i].add(ch)\n",
    "                    cols[j].add(ch)\n",
    "                    sqs[(i // 3) * 3 + (j // 3)].add(ch)\n",
    "                    res.append(ch)\n",
    "\n",
    "                    # 递归填充下一个空格\n",
    "                    if dfs(k+1):\n",
    "                        return True\n",
    "\n",
    "                    # 回溯：如果无法成功填充下一个空格，撤销当前填充，继续尝试其他数字\n",
    "                    res.pop()\n",
    "                    lines[i].remove(ch)\n",
    "                    cols[j].remove(ch)\n",
    "                    sqs[(i // 3) * 3 + (j // 3)].remove(ch)\n",
    "\n",
    "            # 如果无法找到合适的数字填充当前空格，返回False\n",
    "            return False\n",
    "\n",
    "        # 调用DFS函数开始填充数独\n",
    "        dfs(0)\n",
    "\n",
    "        # 将填充结果更新到数独棋盘中\n",
    "        for (i, j), r in zip(empty_list, res):\n",
    "            board[i][j] = r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        lines = [set() for _ in range(9)]\n",
    "        cols = [set() for _ in range(9)]\n",
    "        sqs = [set() for _ in range(9)]\n",
    "        empty_list = []  # 存储空格位置的列表\n",
    "\n",
    "        \n",
    "        for i, line in enumerate(board):\n",
    "            for j, ch in enumerate(line):\n",
    "                if ch == '.':\n",
    "                    empty_list.append((i, j))\n",
    "                else:\n",
    "                    lines[i].add(ch)\n",
    "                    cols[j].add(ch)\n",
    "                    sqs[(i // 3) * 3 + (j // 3)].add(ch)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def dfs(k):\n",
    "            \n",
    "            if k == len(empty_list):\n",
    "                return True\n",
    "\n",
    "            i, j = empty_list[k]\n",
    "\n",
    "            \n",
    "            for ch in '123456789':\n",
    "                if not (ch in lines[i] or ch in cols[j] or ch in sqs[(i // 3) * 3 + (j // 3)]):\n",
    "                   \n",
    "                    lines[i].add(ch)\n",
    "                    cols[j].add(ch)\n",
    "                    sqs[(i // 3) * 3 + (j // 3)].add(ch)\n",
    "                    res.append(ch)\n",
    "\n",
    "                    \n",
    "                    if dfs(k+1):\n",
    "                        return True\n",
    "\n",
    "                    \n",
    "                    res.pop()\n",
    "                    lines[i].remove(ch)\n",
    "                    cols[j].remove(ch)\n",
    "                    sqs[(i // 3) * 3 + (j // 3)].remove(ch)\n",
    "\n",
    "           \n",
    "            return False\n",
    "\n",
    "       \n",
    "        dfs(0)\n",
    "\n",
    "        \n",
    "        for (i, j), r in zip(empty_list, res):\n",
    "            board[i][j] = r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveSudoku(self, board: List[List[str]]) -> None:\n",
    "        def dfs(pos: int):\n",
    "            nonlocal valid\n",
    "            if pos == len(spaces):\n",
    "                valid = True\n",
    "                return\n",
    "            \n",
    "            i, j = spaces[pos]\n",
    "            for digit in range(9):\n",
    "                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "                    board[i][j] = str(digit + 1)\n",
    "                    dfs(pos + 1)\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False\n",
    "                if valid:\n",
    "                    return\n",
    "            \n",
    "        line = [[False] * 9 for _ in range(9)]\n",
    "        column = [[False] * 9 for _ in range(9)]\n",
    "        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]\n",
    "        valid = False\n",
    "        spaces = list()\n",
    "\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                if board[i][j] == \".\":\n",
    "                    spaces.append((i, j))\n",
    "                else:\n",
    "                    digit = int(board[i][j]) - 1\n",
    "                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True\n",
    "\n",
    "        dfs(0)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
